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)$?
Best Answer
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.