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

Question

This definition is extracted from "Introduction to Algorithm, 2nd Edition".

The iterated logarithm function

We use the notation $\lg^* n$ (read "log star of $n$") to denote the iterated logarithm, which is defined as follows. Let $\lg^{(i)} n$ be as defined above, with $f(n) = \lg n$. Because the logarithm of a nonpositive number is undefined, $\lg^{(i)} n$ is defined only if $\lg^{(i-1)} > 0$. Be sure to distinguish $\lg^{(i)}n$ (the logarithm function applied $i$ times in succession, starting with argument $n$) from $\lg^i n$ (the logarithm of $n$ raised to the $i$-th power). The iterated logarithm function is defined as

$$\lg^* n = \min \{i > 0: \lg^{(i)} n ≤ 1\}$$

The iterated logarithm is a very slowly growing function:

$\lg^* 2 = 1$,

$\lg^* 4 = 2$,

$\lg^* 16 = 3$,

$\lg^* 65536 = 4$,

$\lg^* 265536 = 5$.

First, I don't really understand the definition of $\lg^* n$. I haven't met set defined like $\min \{i = 0: ... \}$. What does that mean?

Second, according to the definition of $\lg^* n$, which is asymptotically larger: $\lg(\lg^* n)$ or $\lg^*(\lg n)$?

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

Answer 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. It can be proved by calculating the limit of the quotient of those last two equations (with L'hospital).