# Prove $f(n)=n \log{\log{n}} \notin \Theta (n^k)$ for any $k$

How do I prove $f(n)=n \log{\log{n}} \notin \Theta (n^k)$ for any $k$? I have no idea where to start but I tried plotting the graph in Google and noticed that $\log{\log{n}}$ is very close to 0.

But might it be because it doesn't have a lower bound? Cos as $n \rightarrow 0$, $\log{\log{n}} \rightarrow - \infty$

-
General advice: You care about $n \to \infty$, not $n \to 0$. – ShreevatsaR Feb 4 '13 at 12:49
Do you know the definition of $\Theta(n^k)$ (or $\Theta(g(n))$ in general)? – ShreevatsaR Feb 5 '13 at 7:24

The involved sequence are positive, so we have to see whether there exists $a,b>0$ such that for all $n\geqslant 2$, $$a\leqslant \frac{n\log\log n}{n^k}\leqslant b.$$
• No $k<1$ can work because $n^{1-k}$ diverges to $\infty$.
• $k=1$ neither as $\log\log n\to +\infty$.
• $k>1$ is not good as $\frac{f(n)}{n^a}=\frac{\log\log n}{n^{a-1}}$ is not below bounded.
Erm ... sorry I dont really get what you wanted to say. It will be nice if you could rephrase/elaborate? Sorry I am bad at math ... Or did you mean: diverge to $\infty$ (+/-) means no upper/lower bound? Then by not below bounded means? – Jiew Meng Feb 5 '13 at 2:40