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

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