Which is asymptotically larger: $\lg(\lg^* n)$ or $ \lg^*(\lg n)$?

Solution 1:

Which is asymptotically larger: lg(lg* n) or lg*(lg n)?

I couldn't follow the CLRS definition of $\lg^* n$ so I went to Wikipedia and saw "[lg* n] is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1." When I tried that for the example given in CLRS, it worked as it was supposed to.

Now, I can see that if $\lg^* n = i$ then $\lg^*(\lg n) = i - 1$ since $\lg^*(\lg n)$ is equivalent to another iteration which means we would need one less iteration to get the result less than or equal to 1 (it's even clearer looking at the recursive definition). Thus, if $\lg^* n = i$, then $\lg^*(\lg n) = i - 1$ and $\lg(\lg^* n) = \lg(i)$ so $\lg^*(\lg n)$ is asymptotically larger.

Solution 2:

The prefix $\min$ stands for the minimum of a set - here it apparently means the smallest natural number $k$ such that $\lg^k n \le 1$. Note that, by the definition, $\lg^* 2^m = 1+\lg^*m$, so writing $n=2^m$ (for the purpose of comparing asymptotic growth) reduces the two quantities to $\lg(1+\lg^*m)$ on the left versus $\lg^*m$ on the right; obviously the right-hand side grows exponentially faster.