1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.