Why is $n \log \log n$ not tightly bounded by $n$?

I don't understand why $n \log \log n$ is not $\Theta (n)$.

Suppose we give $n$ a value of $10,000$. Then $n \log \log n$ is $6020.6$. So isn't $n \log \log n$ upper- and lower-bounded by $n$, as $n \log \log n \geq Cn$?

• Hi, I thought 10000(log(log 10000)) is 6020.6? – Malcolm X Mar 5 '13 at 4:03
• Because log 10000 = 4. so it becomes 10000(log(4)) right? – Malcolm X Mar 5 '13 at 4:04
• There is no constant $C$ such that $n \log \log n < C n$, as there is no constant $C$ such that $\log \log n < C$ for all $n$. – vonbrand Mar 5 '13 at 11:17

As $n$ grows bigger, the ratio between $n\log\log n$ and $n$, namely $\log\log n$, tends to infinity. Hence it is not possible to upper bound $n\log\log n \leq Cn$ for any constant $C$. If you stare at this inequality, you discover that the constant $C$ must satisfy $\log\log n \leq C$ for all $n$, yet the function $\log\log n$ is not bounded.

• Hi, I understood most of your explanation, but can you give me a value of n and C where $n\log\log n \leq Cn$ is false? – Malcolm X Mar 5 '13 at 5:14
• No matter what value I give n, $n\log\log n \leq Cn$ seems to hold. 1,000,000 log log 1,000,000 <=1*1,000,000. – Malcolm X Mar 5 '13 at 5:16
• Got it, didn't give n a large enough value! Thanks! =) – Malcolm X Mar 5 '13 at 6:18
• For any given value of $C$, take any $n$ larger than $10^{10^C}$. The point you're missing is that the same value of $C$ has to work for all $n$. – Yuval Filmus Mar 5 '13 at 6:18

You could not narrow $f(x) = x\log \log x$ with $g = n$, because inequalities that must be met for this, never occur. Remember that the logarithm function is always increasing. So, If We had it, $f$ should perform the next inequalite for some constants $c$ and $C$. $$cn\leq f \leq Cn$$

Let's see that, for example a right side of these inequalities and see the contradiction.

\begin{align} x\log \log x \leq cx\\ e^{x\log \log x }\leq e^{cx}\\ e^x\log x \leq e^{cx}\\ \log x \leq e^c \end{align} So, you are saying that $\log x \leq k$, for any $x\in R$, that's not true.

• Hi, I understood most of your explanation, but can you give me a value of n and C where $n \log \log n \leq Cn$ is false? – Malcolm X Mar 5 '13 at 5:25
• If I have 1 for the C value, the statement $n \log \log n \leq Cn$ always seems to be true! Am I missing something? – Malcolm X Mar 5 '13 at 5:28
• @MalcolmX: For $C=1$, pick $n = 10^{100}$, since you seem to be assuming the $\log$ is to base $10$. – Aryabhata Mar 5 '13 at 6:15

Simply, because $\log\log n$ is not a constant! actually, $$\lim_{n\to \infty} \log\log n = \infty$$

while for some function to be $\Theta(n)$ it is required that it is bounded by $cn$ for some constant $c$.

tl;dr you didn't look at large enough $n$'s. try $n$ = Graham's number.

• Well, $f(n) = 1$ if $n$ is prime, otherwise $f(n) = 2$ is not constant either, but $n f(n) = \theta(n)$. – Aryabhata Mar 5 '13 at 6:11
• @Aryabhata you are right, but I said "bounded by a constant". $c=3$ works for your example (as an upper bound). – Ran G. Mar 5 '13 at 6:13
• Got it, thanks! :) I will upvote your answer when I can! – Malcolm X Mar 5 '13 at 6:16
• I was only disputing the first statement which does not have the word bounded in it :-) – Aryabhata Mar 5 '13 at 6:16