patternModerate
Why is $n \log \log n$ not tightly bounded by $n$?
Viewed 0 times
tightlywhylogboundednot
Problem
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$?
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$?
Solution
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.
Context
StackExchange Computer Science Q#10281, answer score: 10
Revisions (0)
No revisions yet.