# Is $\log^{*}(\log(n)) = \Theta (\log(\log^{*}(n)))$?

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).

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$$.
Suppose $$f_1(n)=\log \log^{*}(n)$$, and $$f_{2}(n)=\log^{*} \log(n)$$.
Let $$n=2^m$$ then According the definition of iterated function:
$$\log^* n$$ (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1.
So $$f_1(2^m)=\log \log^*(2^m)=\log \log^*\log(2^m)+1=\log\log^*m+1=\theta(\log\log^*m)$$
and $$f_2(2^m)=\log^*\log(2^m)=\log^*(m)+1=\theta(\log^*m)$$ Finally, for sufficient large $$n$$ (i.e. as $$n\to \infty$$) we conclude that: $$f_1(2^m)=O(f_2(2^m)).$$ Because let $$\log^*(m)=k$$ then: $$f_1(2^m)=\log k$$ and $$f_2(2^m)=k.$$ Obviously order of growth two mentioned function follow below relation $$f_1(2^m)=O(f_2(2^m)).$$