Which is asymptotically larger: \(\lg(\lg^\ast n)\) or \(\lg^\ast (\lg n)\)?
Here is how \(\lg^\ast n\) is defined mathematically:
\[\lg^\ast n = \min \{i \geq 0 : lg^{(i)} n \leq 1\}\]Which practically means, \(\lg^* n\) is the number of times the logarithm (base \(2\)) function can be iteratively applied to \(n\) before the result is less than or equal to 1.
Let us assume \(\lg^* n = x\).
So, \(\lg(\lg^* n) = \lg x\)
And, \(\lg^*(\lg n) = x - 1\) as we are applying logarithm once more thus reducing number of required iterations by 1.
Now, asymptotically:
\[\begin{aligned} x - 1 &> \lg x \\ \lg^\ast (\lg n) &> \lg(\lg^\ast n) \end{aligned}\]