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}\]