Iterated logarithm

The iterated logarithm $\lg^* n$ is the number of times the binary logarithm must be applied to $n$ before the result is at most 1. It grows more slowly than $\lg \lg n$, $\lg \lg \lg n$ and every fixed number of nested logarithms. For each input size $n$ that occurs in practice, $\lg^* n \le 5$. It appears in the cost of coloring a cycle in a distributed system and in an old bound for union-find.

Definition

Let $\lg^{(0)} x = x$ and $\lg^{(i+1)} x = \lg(\lg^{(i)} x)$, defined as long as $\lg^{(i)} x > 0$. For a real number $x$, the iterated logarithm is

Do not confuse $\lg^{(i)} x$, the $i$-fold composition, with $\lg^i x = (\lg x)^i$, a power.

The minimum exists for each real $x$. If $x \le 1$, the set contains $i = 0$, so $\lg^* x = 0$. Else the steps stay defined, because a value $y > 1$ gives $\lg y > 0$. Two facts show that the values reach 1. First, for $y > 2$ we have $\lg y < y - 1$, because $\lg$ is concave and equals $y - 1$ at $y = 1$ and $y = 2$, so it is below this line for $y > 2$. Second, for $1 < y \le 2$ we have $0 < \lg y \le 1$. So while the value is above 2, each step lowers it by more than 1, and after at most $\lceil x \rceil$ steps it is at most 2. One more step makes it at most 1. The site uses the function for integers $n \ge 1$.

The definition gives the recurrence

Compare this with the tower function $T(0) = 1$, $T(k+1) = 2^{T(k)}$. Then $T(1) = 2$, $T(2) = 4$, $T(3) = 16$, $T(4) = 65536$, $T(5) = 2^{65536}$. For $k \ge 1$ and each real $x$:

Proof. Induction on $k$. For $k = 1$: $\lg^* x = 1$ means $x > 1$ and $\lg x \le 1$, that is $1 < x \le 2$. For the step, let $k \ge 2$. Both sides need $x > 1$: the left side because $\lg^* x = 0$ for $x \le 1$, the right side because $T(k-1) \ge 2$. For $x > 1$, the recurrence gives $\lg^* x = k$ exactly when $\lg^*(\lg x) = k - 1$. By the hypothesis this holds exactly when $T(k-2) < \lg x \le T(k-1)$. Since $\lg$ is increasing and $\lg T(j) = T(j-1)$ for $j \ge 1$, this is the same as $T(k-1) < x \le T(k)$. $\square$

So $\lg^*$ is the inverse of the tower function. For $n = 1$ the value is 0.

Examples and non-examples

$n$	$\lg^* n$
1	0
2	1
3, 4	2
5 to 16	3
17 to 65536	4
65537 to $2^{65536}$	5

The number $2^{65536}$ has 19729 decimal digits. The number of atoms in the observable universe is often estimated as about $10^{80}$, a number with 81 digits. So no input with more than $2^{65536}$ items or bits can be stored, and $\lg^* n \le 5$ for each input size $n$ that occurs in practice. A single stored number can be larger: $2^{65537}$ needs only 65538 bits, and $\lg^* 2^{65537} = 6$.

Examples of the computation:

• $n = 16$: $16 \to 4 \to 2 \to 1$, three steps. So $\lg^* 16 = 3$.
• $n = 65536$: $65536 \to 16 \to 4 \to 2 \to 1$, four steps.
• $n = 65537$: since $T(4) = 65536 < 65537 \le T(5)$, the rule gives $\lg^* 65537 = 5$. By steps: $\lg 65537 \approx 16.00002$, which is above $T(3) = 16$, so four more steps are necessary.

Comparison with $\lg \lg n$. At $n = 2^{65536}$, $\lg n = 65536$ and $\lg \lg n = 16$, but $\lg^* n = 5$. At $n = 10^6$, $\lg \lg n \approx 4.3$ and $\lg^* n = 5$ (as $10^6 > 65536$), so for small $n$ the two can be close. As $n$ grows, $\lg \lg n$ grows without bound much faster: $\lg^* n = o(\lg \lg n)$, and the same holds for $\lg^{(c)} n$ for each fixed $c$. Proof: if $\lg^* n = k \ge c + 2$, then $n > T(k-1)$, so $\lg^{(c)} n > T(k-1-c)$. Since $T(j) \ge 2^j$, the ratio $\lg^{(c)} n / \lg^* n$ is more than $2^{k-1-c}/k$, which tends to infinity with $k$.

Non-examples. The iterated logarithm is not the iterated power $(\lg n)^k$, and it is not $\lg \lg n$. It is also not the inverse Ackermann function $\alpha(n)$: $\alpha$ grows even more slowly than $\lg^*$ (see below).

Related definitions

• Where $\lg^*$ appears.
  • Coloring a cycle. Cole and Vishkin gave a deterministic method for a cycle (or a linked list) of $n$ nodes with distinct identifiers from $\{1, \dots, n\}$ in which each node knows its successor. In each synchronous round, a node compares its color with its successor's color, and finds the lowest bit where they differ. The new color is a function of the position of this bit and its value. A color with $k$ bits is replaced by a color with about $\lg k + 1$ bits, so after $O(\lg^* n)$ rounds only a constant number of colors remain. A few more rounds give 3 colors. Cole and Vishkin used this step for parallel list ranking. Linial (1992) proved that each deterministic distributed algorithm that 3-colors a cycle of $n$ nodes needs $\Omega(\lg^* n)$ rounds, so the bound of Cole and Vishkin is tight up to a constant factor.
  • Integer multiplication. Fürer (2007) multiplied two $n$-bit integers in $n \lg n \cdot 2^{O(\lg^* n)}$ bit operations. Harvey and van der Hoeven (2021) later removed the factor $2^{O(\lg^* n)}$ and reached $O(n \lg n)$. See integer multiplication.
  • Union-find. Hopcroft and Ullman (1973) proved that a sequence of $m$ operations on $n$ elements takes $O(m \lg^* n)$ time when the structure links trees by size and uses path compression. The same bound holds for union by rank (see union by rank and disjoint-set forest).
• The bound of Tarjan. Tarjan (1975) gave a tighter bound for the same structure: $O(m\,\alpha(m, n))$, where $\alpha$ is the inverse Ackermann function. The function $\alpha$ grows more slowly than $\lg^*$, so the bound with $\alpha$ is stronger, and the bound with $\lg^*$ is the older and weaker one. Both bounds are for the same data structure. The Ackermann function page has the definitions of $\alpha$, and the page on the amortized bound of union-find has the details.
• Not a constant, but nearly. The function $\lg^* n$ is unbounded, so $\lg^* n \ne O(1)$. A bound with $\lg^*$ is therefore not linear. But the factor $\lg^* n$ is at most 5 for each practical $n$, so the bound is linear up to a small constant factor.

References

1. Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, fourth edition, Chapter 3, standard notations and common functions (iterated logarithm)
2. Hopcroft and Ullman, Set merging algorithms, SIAM Journal on Computing 2 (1973), the O(m lg* n) bound for union by rank with path compression
3. Cole and Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control 70 (1986), the coloring of a cycle in O(lg* n) rounds
4. Tarjan, Efficiency of a good but not linear set union algorithm, Journal of the ACM 22 (1975), the bound with the inverse Ackermann function
5. Nathan Linial, Locality in distributed graph algorithms, SIAM Journal on Computing 21 (1992), the lower bound for coloring a cycle
6. Martin Fürer, Faster integer multiplication, STOC 2007, the main theorem
7. David Harvey and Joris van der Hoeven, Integer multiplication in time O(n log n), Annals of Mathematics 193 (2021), the main theorem