Problem Detail: 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$?
Asked By : Malcolm X
Answered By : Yuval Filmus
As $n$ grows bigger, the ratio between $nloglog n$ and $n$, namely $loglog n$, tends to infinity. Hence it is not possible to upper bound $nloglog n leq Cn$ for any constant $C$. If you stare at this inequality, you discover that the constant $C$ must satisfy $loglog n leq C$ for all $n$, yet the function $loglog n$ is not bounded.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10281
