Proof $(\log(n))^{\log(\log(n))} = O(n)$

Question

Can someone provide a proof that $(\log(n))^{\log(\log(n))} = O(n)$? Preferably without calculus, but I'll take what I can get. Just ran into this problem, and I have no way of moving forward, especially considering $\log(n)^{\log(n)} \not= O(n)$.

Answer 1

Since $$ \lim_{x\to+\infty}\frac{\log x}{x^a}=0 $$ for $a>0$, we also get that (with $a=1/2$) $$ \lim_{x\to+\infty}\frac{(\log x)^2}{x}=\lim_{x\to+\infty}\Bigl(\frac{\log x}{x^{1/2}}\Bigr)^2=0. $$ Now, let $x=\log n$, and you get $$ \frac{\bigl(\log(\log(n))\bigr)^2}{\log n}\to 0\quad\text{as}\quad n\to+\infty. $$ Thus $$ (\log n)^{\log(\log(n))}=\exp\bigl(\log(\log(n))\log(\log(n))\bigr)=O(\exp(\log n))=O(n). $$ You could even make those big O small o's if you'd like.