patternMinor
Is $\log^{*}(\log(n)) = \Theta (\log(\log^{*}(n)))$?
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.