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

Question

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 04 '13 at 12:49
Do you know the definition of $\Theta(n^k)$ (or $\Theta(g(n))$ in general)? — ShreevatsaR, Feb 05 '13 at 07:24

Davide Giraudo · Accepted Answer · 2013-02-05T09:36:58.077

2

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.

edited Feb 05 '13 at 09:36

answered Feb 04 '13 at 11:12

Davide Giraudo

172,925

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 05 '13 at 02:40
@JiewMeng I've added details. Don't hesitate to ask me more clarifications. – Davide Giraudo Feb 05 '13 at 09:37

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

1 Answers1