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.

For my algorithms course I am studying the definition of the iterated logarithm function (and functional iteration in general) and I don't quite understand the set notation used (it's been quite a few years since I last looked at set notation). Could someone please explain this definition?

$$ \lg^{\ast} n = \min \{ i \ge 0 \,:\, \lg^i n \le 1 \} .$$

share|improve this question
2  
It simply means ‘the least non-negative $i$ such that the $i$-fold iterated logarithm of $n$ is at most $1$.’ What precisely about the notation is causing you trouble? –  Zhen Lin Sep 23 '11 at 0:50
add comment

3 Answers

up vote 4 down vote accepted

The notation defines $\lg^*(n)$ as the minimum element of the set $\{ i\ge 0\mid \lg^i(n) \le 1 \}$

The set $\{ i\ge 0\mid \lg^i(n) \le 1 \}$ (which can be notated either with a colon or a vertical bar, purely down to author preferences) is the set of all $i\ge 0$ such that $\lg^i(n)\le 1$. Strictly speaking the notation ought to say which set we pull the $i$'s from, but in this case we can guess that it's probably the integers -- otherwise the rest of the expression would not make sense.

$\lg^i(n)$ is the $\lg$ function iterated $i$ times and applied to $n$. For example, $\lg^5(25)$ means $\lg(\lg(\lg(\lg(\lg(25)))))$.

$\lg$ is a logarithm. It doesn't say exactly which base it has, but in algorithmics the tradition is to use base-2 logarithms unless something else is stated explicitly, so we can assume that is the case.

Thus, $\lg^*(n)$ is the number of times we need to take successive base-2 logarithms of $n$ before we reach a number less than $1$. This is a very slow-growing function; let's compute $\lg^*(10^9)$:

$$\lg(10^9)=28.9$$ $$\lg^2(10^9)=\lg(28.9)=4.8$$ $$\lg^3(10^9)=\lg(4.8)=2.3$$ $$\lg^4(10^9)=\lg(2.3)=1.2$$ $$\lg^5(10^9)=\lg(1.2)=0.26$$ so $\lg^*(10^9)=5$. This is in practice the maximum value for $\lg^*$ -- it only becomes 6 for $n>2^{65536}$, which is so much larger than, say, the number of atoms in the known universe that it isn't even funny.

share|improve this answer
    
+1 Nice answer. Somewhat confusingly, the notation $\lg x$ is the ISO standard for $\log_{10} x$. :) I haven't come across this base-10 usage though. –  Srivatsan Sep 23 '11 at 2:16
add comment

So, the thing in braces is a set. The things on the left of the colon define a set by themselves, and then the things on the right of the colon define a restriction that makes a subset. In this case, the set you start out with is all numbers (presumably integers) greater than or equal to 0, and the restriction is that a number i from this range is in your set if, when the lg function is iterated i times on your argument n, you get a value less than or equal to 1. The "min" means in this case the smallest integer in this set. So this is a fancy way of saying "the smallest number such that when you iterate the lg function that many times you get a result less than 1."

share|improve this answer
add comment

In this context I would expect $\lg^i$ to mean taking the logarithm $i$ times. For example $\lg^3 x$ would mean $\lg(\lg(\lg(x)))$.

So $\lg^*$ means count the number of times you need to take the logarithm until you reach 1 or less.

If $\lg$ is $\log_{10}$ then

  • $\lg^* n =0$ when $n \le 1$
  • $\lg^* n =1$ when $1 \lt n \le 10$
  • $\lg^* n =2$ when $10 \lt n \le 10^{10}$
  • $\lg^* n =3$ when $10^{10} \lt n \le 10^{10^{10}}$ etc.
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.