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

Setting \(x = \lg^* n\) gives us \(\lg(\lg^* n) = \lg x\). It also gives us \(\lg^*(\lg n) = x - 1\) because the inner logarithm of \(\lg^*(\lg n)\) reduces the output of the iterated logarithm by 1.

Because \(x - 1\) is asymptotically larger than \(\lg(x)\), \(\lg^*(\lg n)\) is also asymptotically larger than \(\lg(\lg^* n)\).