# $(\log n)^{\log n}$ lower-bound and upper-bound

we know that $$n \geq \log{n}$$ however I understand that $$(\log n)^{\log n}$$ grows faster than $$n$$. I have been trying to prove this however I can't seem to figure it out.

• Please don't delete your question after you've received an answer. Part of our mission is to build up an archive of high-quality questions and answers that will be useful not only to the person who asked but also to others in the future. Deleting the question can be considered impolite to the answerer who spent time to write out an answer, with this understanding in mind. Thank you for your understanding. – D.W. May 24 at 3:08

Here is a way to show it without limits. Let $$n = 2^x$$. Now you are comparing the growth rates of $$2^x$$ and $$x^x$$.
$$\lim_{n \to \infty} \frac{(\log n)^{\log n}}{n} = \lim_{n \to \infty} \frac{2^{\log ( (\log n)^{\log n})}}{n} = \lim_{n \to \infty} \frac{2^{(\log n) \cdot \log \log n}}{n} = \lim_{n \to \infty} \frac{n^{\log \log n}}{n} = \lim_{n \to \infty} n^{\log \log n -1} = +\infty.$$
• For $n \ge 2^{2^k}$ you have $(\log n)^{\log n} = n^{\log \log n} \ge n^k$ . This shows that $(\log n)^{\log n} = \Omega(n^k)$ for any constant $k$. If you only care about showing that $(\log n)^{\log n} = \omega(n)$ you can pick, e.g., $k=2$. – Steven May 23 at 23:36
• That's precisely what I wanted to show yes, I however haven't really brushed up on my logarithms which is probably why this was harder for me to show, how exactly do we go from $(\log{n})^{\log{n}} = n ^{\log{\log{n}}}$? – ediblebanana May 23 at 23:52
• Using exactly the same steps in my answer. The properties I'm using are $x = 2^{\log x}$, $\log x^y = y \log x$ , and $2^{xy} = (2^x)^y$. The base of all logarithms is $2$. – Steven May 23 at 23:55