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)$.
Asked
Active
Viewed 107 times
1
-
This notation is a bit ambiguous. What does $\log^{\log(\log(n))}$ mean? – jimjim Jan 30 '15 at 07:44
-
I updated the problem. – Jan 30 '15 at 07:44
-
does $\log(n)^{\log(\log(n))} $ mean $\log(n^{\log(\log(n))}) $ or $(\log n)^{\log(\log(n))} $? – jimjim Jan 30 '15 at 07:46
-
The latter. Sorry, I'll fix that. – Jan 30 '15 at 07:47
1 Answers
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.
mickep
- 19,962
-
Why is the first limit true? I think I believe it, but could you be more explicit? – Jan 30 '15 at 07:54
-
I updated with an explanation. Remember that $\log x$ grows very slowly... – mickep Jan 30 '15 at 07:59
-
1@Anthony Possibly the most fundamental tool in the asymptotics toolbox is that $\log(n)$ is in $o(n^a)$ as $n\to\infty$ for any $a\gt 0$ (and so as a result, $\log(n)^a$ is in $o(n^b)$ as $n\to\infty$ for any $a,b\gt 0$.) Informally, any power of $\log n$ grows slower than any power of $n$. – Steven Stadnicki Jan 30 '15 at 08:02