0
$\begingroup$

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 \} .$

  • 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? – 2011-09-23

3 Answers 3

5

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.

  • 0
    @DavidK: In computer science it is not uncommon to write $\log x$ to mean $\log_2 x$ too. – 2014-10-11
0

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."

0

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.