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$?
4
$\begingroup$
$\endgroup$
-
$\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
10
$\begingroup$
$\endgroup$
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.
answered Mar 5 '13 at 4:37
-
$\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
4
$\begingroup$
$\endgroup$
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
3
$\begingroup$
$\endgroup$
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
