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

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)$?

-
Should that be i>0? –  Joe Aug 5 '11 at 2:25
You're right, there's a typo in the version I'm reading. –  ablmf Aug 5 '11 at 2:30
According to Wikipedia, "the iterated logarithm of n... is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1." So I believe Matt is right that it should be $i \ge 0$, and $\min\{i \ge 0 : \ldots\}$ simply means $\min\{i : i \ge 0, \ldots\}$. –  Rahul Aug 5 '11 at 2:30
@abmlf: I wonder why you just deleted this other question: math.stackexchange.com/questions/57250 (and furthermore, after having deleted some comment you had made, if I remember correctly). This is odd, but maybe you have an explanation. –  Did Aug 13 '11 at 21:52
@Didier: Ah, I thought my comment might be a little bit inappropriate and since the question did get any answers, maybe I shouldn't leave it there anymore. Anyway, thanks for you attention. –  ablmf Aug 14 '11 at 2:30

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 righthand side grows exponentially faster.

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