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