Iterated logarithm

In computer science, the iterated logarithm of ${\displaystyle n}$, written log* ${\displaystyle n}$ (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to ${\displaystyle 1}$.^[1] The simplest formal definition is the result of this recurrence relation:

${\displaystyle \log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}}$

In computer science, lg* is often used to indicate the binary iterated logarithm, which iterates the binary logarithm (with base ${\displaystyle 2}$) instead of the natural logarithm (with base e). Mathematically, the iterated logarithm is well defined for any base greater than ${\displaystyle e^{1/e}\approx 1.444667}$, not only for base ${\displaystyle 2}$ and base e. The "super-logarithm" function ${\displaystyle \mathrm {slog} _{b}(n)}$ is "essentially equivalent" to the base ${\displaystyle b}$ iterated logarithm (although differing in minor details of rounding) and forms an inverse to the operation of tetration.^[2]

The iterated logarithm is useful in analysis of algorithms and computational complexity, appearing in the time and space complexity bounds of some algorithms such as:

• Finding the Delaunay triangulation of a set of points knowing the Euclidean minimum spanning tree: randomized O(n log* n) time.^[3]
• Fürer's algorithm for integer multiplication: O(n log n 2^O(lg* n)).
• Finding an approximate maximum (element at least as large as the median): lg* n − 1 ± 3 parallel operations.^[4]
• Richard Cole and Uzi Vishkin's distributed algorithm for 3-coloring an n-cycle: O(log* n) synchronous communication rounds.^[5]

The iterated logarithm grows at an extremely slow rate, much slower than the logarithm itself, or repeats of it. This is because the tetration grows much faster than iterated exponential:

$${\displaystyle {^{y}b}=\underbrace {b^{b^{\cdot ^{\cdot ^{b}}}}} _{y}\gg \underbrace {b^{b^{\cdot ^{\cdot ^{b^{y}}}}}} _{n}}$$

the inverse grows much slower: ${\displaystyle \log _{b}^{*}x\ll \log _{b}^{n}x}$.

For all values of n relevant to counting the running times of algorithms implemented in practice (i.e., n ≤ 2⁶⁵⁵³⁶, which is far more than the estimated number of atoms in the known universe), the iterated logarithm with base 2 has a value no more than 5.

Higher bases give smaller iterated logarithms.

The iterated logarithm is closely related to the generalized logarithm function used in symmetric level-index arithmetic. The additive persistence of a number, the number of times someone must replace the number by the sum of its digits before reaching its digital root, is ${\displaystyle O(\log ^{*}n)}$.

In computational complexity theory, Santhanam^[6] shows that the computational resources DTIME — computation time for a deterministic Turing machine — and NTIME — computation time for a non-deterministic Turing machine — are distinct up to ${\displaystyle n{\sqrt {\log ^{*}n}}.}$

• Inverse Ackermann function, an even more slowly growing function also used in computational complexity theory