# Homework Help: Give a big-O estimate of the product of the first n odd positive integers

1. Jul 17, 2011

### pc2-brazil

1. The problem statement, all variables and given/known data
Give a big-O estimate of the product of the first n odd
positive integers.

2. Relevant equations
Big-O notation:
f(x) is O(g(x)) if there are constants C and k such that
|f(x)| ≤ C|g(x)| whenever x > k.

3. The attempt at a solution
The product of the first n odd integers can be given by:
$$P(n)=1\times 3\times 5\times 7\times...\times (2n-1)$$
For n > 0, no element in the above sequence will be greater than (2n-1). Thus:
$$1\times 3\times 5\times 7\times...\times (2n-1)\leq (2n-1)\times (2n-1)...\times (2n-1)=(2n-1)^n$$
So:
P(n) ≤ (2n-1)n whenever n > 0
I could stop here and say that
P(n) is O((2n-1)n)
But to simplify I think I could consider that:
P(n) ≤ (2n-1)n ≤ (2n)n
Thus,
P(n) is O((2n)n)

Is this reasoning correct?

Last edited: Jul 17, 2011
2. Jul 17, 2011

### tiny-tim

hi pc2-brazil!

it's correct, but it's not very accurate, is it?

do you know a big-O estimate for n! ?

3. Jul 17, 2011

### pc2-brazil

A big-O estimate for n! would be O(nn).
I could say that, for n > 0,
$$1\times 3\times 5\times 7...\times (2n-1)\leq 1\times 2\times 3\times 4\times...\times (2n-1)=(2n-1)!\leq (2n)!=2^n n!$$
Thus, P(n) is O(2nn!). Since n! is O(nn), this estimate seems more accurate than the previous one (O(2nnn)).

4. Jul 17, 2011

### tiny-tim

Last edited by a moderator: Apr 26, 2017
5. Jul 17, 2011

### Ray Vickson

If En = product of the even numbers from 2 to 2n - 2, your product is (2n-1)!/En, and En = 2^(n-1) * (n-1)! Now apply Stirling's formula to both factorials. Note: if you want a true upper bound, rather than just an *estimate* you can use the fact that if St(n) is defined as
sqrt(2pi)*n^(n + 1/2)*exp(-n), then we have St(n) <n! < St(n)*exp(1/(12n)), even if n is not large. You can use the upper bound on (2n-1)! in the numerator and the lower bound on (n-1)! in the denominator.

RGV

sqrt(2pi)*n