HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

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

Submitted by: @import:stackexchange-cs··
0
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$?

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.