# $(\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
• First specify the base of the logarithm, because that makes a difference. Aug 4 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? May 23 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$. 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}}}$? 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$. May 23 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)$$.