If $\lg(n!) = \Theta(n \lg n)$, does $\lg(n!) = \Theta(\lg(n^{n^n}))$ as well?

85 Views Asked by At

First consider that we have:

$$ \begin{align} \lg(n!) &= \overbrace{\lg\Bigg(\sqrt{2\pi{n}}\Big(\frac{n}{e}\Big)^n\Big(1+\Theta(\frac{1}{n})\Big)\Bigg)}^{\text{Stirling's Equality}} = \lg\sqrt{2\pi{n}} + \lg\Big(\frac{n}{e}\Big)^n + \lg\Big(1+\Theta(\frac{1}{n})\Big) = \\ &= \Theta(\sqrt{n}) + n\lg{\frac{n}{e}} + \lg\Big(\Theta(1) + \Theta(\frac{1}{n})\Big) = \Theta(\sqrt{n}) + \Theta(n\lg{n}) + \Theta(\frac{1}{n}) = \\ &= \Theta(n\lg{n}) \\ &= \Theta(\lg{n^n}) \end{align} $$

This to me is a stunning fact given that $n! = o(n^n)$. So I suppose, intuitively, that the "contracting force" of $\lg$ is stronger than the "explosive force" of $n^n$? But where does this end?

Question: Is it also true that $\lg(n!) = \Theta(\lg(n^{n^n}))$?