Question

Give a Big-O estimate of the product of first n odd positive integers.

Short answer

A Big-O estimate of the product of the first n odd positive integers is O (2ⁿn!)

Step-by-step solution

Step 1

Let k=1 when n>1.

We can choose any value of k, which gives different values of M.

Step 2

Now consider,

│f(n)│= │1×3×5×…×(2n-1)│ (sum of n odd positive integers)

= 1×3×5×…×(2n-1)

≤2×4×6×…×2n (x≤ x+1)

= (2×1) × (2×2) ×( 2×3) ×…×(2×n)

=2ⁿ × (1×2×3×…×n) (n!= 1×2×3×…×n)

= 2ⁿn!

Thus, we choose M atleast to be 1. Let M=1.

By the definition of Big-O notation,

f (n)= 1×3×5×…×(2n-1) is O(2ⁿn!) with k=1 and M=1.

Final answer

A Big-O estimate of the product of the first n odd positive integers is O (2ⁿn!)