Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers

up vote 6 down vote accepted

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.

share|improve this answer
add comment
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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.