11
$\begingroup$

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

  • 0
    @Didier: Ah, I thought my comment might be $a$ little bit inappropriate and since the question did get an$y$ answers, ma$y$be I shouldn't leave it there an$y$more. An$y$w$a$y, thanks for you attention.2011-08-14

2 Answers 2

7

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.

  • 0
    Is it possible to add more explanation why one of these is asymptotically larger? nice answer but not simple for me :)2016-07-26
7
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.