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

Is $\log^{*}(\log(n)) = \Theta (\log(\log^{*}(n)))$?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thetalogstackoverflow

Problem

Which one is asymptotically larger? $\log^(\log(n))$ or $\log(\log^(n))$? I think they are asymptotically tight bounds for each other (one is $\Theta$ of the other).

Solution

Suppose that $\log^ n = k$. This means it takes $k$ many $\log$'s to reduce $n$ below some constant. Therefore $\log^ \log n = k-1$ (assuming $k$ is not too small), whereas $\log \log^* n = \log k$.

Context

StackExchange Computer Science Q#141925, answer score: 4

Revisions (0)

No revisions yet.