Thursday, January 25, 2018

logarithms - Using Stirling's approximiation to show that $(log(log n))!$ is $O(n^k)$



I am trying to show the following:




Prove, using Stirling's approximiation, that $(\log(\log n))!$ is $O(n^k)$ for some positive constant $k$. Stirling's approximation is
$$n!=\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(1+\Theta\left(\frac{1}{n}\right)\right).$$




By the given formula,

$$(\log(\log n))!=\sqrt{2\pi\log(\log n)}\left(\frac{\log(\log n)}{e}\right)^{\log(\log n)}\left(1+\Theta\left(\frac{1}{\log(\log n)}\right)\right).$$



I can show that $\sqrt{2\pi\log(\log n)}$ is $O(n^{1/2})$ and that $1+\Theta\left(\frac{1}{\log(\log n)}\right)$ is $O(1)$, but I am having trouble showing that $\left(\frac{\log(\log n)}{e}\right)^{\log(\log n)}$ is $O(n^k)$.



I can take the logarithm of this term and get $\approx(\log(\log n))(\log(\log(\log n)))$, but I am not sure where to go from here.


Answer



It's easier if you redefine $t = \log \log n$, then RHS becomes $e^{e^{kt}}$. Now apply Stirling's approximation to the LHS and take logarithm. You'll see that lhs is $t \log t -t +O(\log t)$, which is of course $O(e^{kt})$.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...