$(\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.
Commented May 24, 2021 at 3:08
• First specify the base of the logarithm, because that makes a difference. Commented Aug 4, 2021 at 9:11

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

• yes thank you! i did try it with limits but is there any way to show it without using limits? Commented May 23, 2021 at 23:33
• 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$. Commented May 23, 2021 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}}}$? Commented May 23, 2021 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$. Commented May 23, 2021 at 23:55

We can show that $$n=o\left(\log^{\log n} n\right)$$.

Consider another form of $$(\log^{\log n} n)$$: $$\left(\log^{\log n} n\right)=n^{\log\log n}$$ $$=\prod_{k=1}^{\log\log n}n=\underbrace{n\times n\times \dots\times n}_{\log\log n \text{ times}}$$

Hence $$n< \underbrace{n\times n\times\dots\times n}_{\log\log n \text{ times}}.$$ So $$n=o\left(\log^{\log n} n\right)$$.