patternModerate
Asymptotics question
Viewed 0 times
asymptoticsquestionstackoverflow
Problem
Is $\frac {n!} {2!\cdot 4!\cdot 8!\dots (n/2)!}=O(4^n)$?
I am really stuck and I tend to believe it's true, but I don't know how to prove it.
Any help would be appreciated!
I am really stuck and I tend to believe it's true, but I don't know how to prove it.
Any help would be appreciated!
Solution
We have
$$
\frac{n!}{(n/2)!(n/4)!\cdots 2!} =
\frac{n!}{(n/2)!(n/2)!} \frac{(n/2)!}{(n/4)!(n/4)!} \cdots \frac{4!}{2!2!} \frac{2!}{1!1!} = \\
\binom{n}{n/2} \binom{n/2}{n/4} \cdots \binom{4}{2} \binom{2}{1} \leq 2^n 2^{n/2} \cdots 2^4 2^2 = 2^{n+n/2+\cdots+2+1} <2^{2n} = 4^n.
$$
Using Stirling's approximation we can get more refined asymptotics, but we leave this to the interested reader.
$$
\frac{n!}{(n/2)!(n/4)!\cdots 2!} =
\frac{n!}{(n/2)!(n/2)!} \frac{(n/2)!}{(n/4)!(n/4)!} \cdots \frac{4!}{2!2!} \frac{2!}{1!1!} = \\
\binom{n}{n/2} \binom{n/2}{n/4} \cdots \binom{4}{2} \binom{2}{1} \leq 2^n 2^{n/2} \cdots 2^4 2^2 = 2^{n+n/2+\cdots+2+1} <2^{2n} = 4^n.
$$
Using Stirling's approximation we can get more refined asymptotics, but we leave this to the interested reader.
Context
StackExchange Computer Science Q#107255, answer score: 18
Revisions (0)
No revisions yet.