Figure 1. Demonstrating log* 4 = 2 for the base-e iterated logarithm. The value of the iterated logarithm can be found by "zig-zagging" on the curve y = logb(x) from the input n, to the interval [0,1]. In this case, b = e. The zig-zagging entails starting from the point (n, 0) and iteratively moving to (n, logb(n) ), to (0, logb(n) ), to (logb(n), 0 ).
In computer science, the iterated logarithm of , written log* (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 .[1] The simplest formal definition is the result of this recurrence relation:
In computer science, lg* is often used to indicate the binary iterated logarithm, which iterates the binary logarithm (with base ) instead of the natural logarithm (with base e). Mathematically, the iterated logarithm is well defined for any base greater than , not only for base and base e. The "super-logarithm" function is "essentially equivalent" to the base iterated logarithm (although differing in minor details of rounding) and forms an inverse to the operation of tetration.[2]
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:
the inverse grows much slower: .
For all values of n relevant to counting the running times of algorithms implemented in practice (i.e., n ≤ 265536, 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.