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$?

  • $\begingroup$ Hi, I thought 10000(log(log 10000)) is 6020.6? $\endgroup$ – Malcolm X Mar 5 '13 at 4:03
  • $\begingroup$ Because log 10000 = 4. so it becomes 10000(log(4)) right? $\endgroup$ – Malcolm X Mar 5 '13 at 4:04
  • $\begingroup$ 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$. $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – Malcolm X Mar 5 '13 at 5:14
  • $\begingroup$ 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. $\endgroup$ – Malcolm X Mar 5 '13 at 5:16
  • $\begingroup$ Got it, didn't give n a large enough value! Thanks! =) $\endgroup$ – Malcolm X Mar 5 '13 at 6:18
  • 4
    $\begingroup$ 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$. $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – Malcolm X Mar 5 '13 at 5:25
  • $\begingroup$ 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? $\endgroup$ – Malcolm X Mar 5 '13 at 5:28
  • $\begingroup$ @MalcolmX: For $C=1$, pick $n = 10^{100}$, since you seem to be assuming the $\log$ is to base $10$. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.