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

[pc2-brazil]

Homework Statement

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

Homework 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.

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)ⁿ whenever n > 0
I could stop here and say that
P(n) is O((2n-1)ⁿ)
But to simplify I think I could consider that:
P(n) ≤ (2n-1)ⁿ ≤ (2n)ⁿ
Thus,
P(n) is O((2n)ⁿ)

Is this reasoning correct?

Thank you in advance.

 

[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! ? ​

 

[pc2-brazil]

hi pc2-brazil!

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

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

A big-O estimate for n! would be O(nⁿ).
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(2ⁿn!). Since n! is O(nⁿ), this estimate seems more accurate than the previous one (O(2ⁿnⁿ)).

 

[tiny-tim]

A big-O estimate for n! would be O(nⁿ).

ah, see http://en.wikipedia.org/wiki/Factorial#Rate_of_growth"

 

[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