Iterated logarithm

In computer science, the iterated logarithm of n {displaystyle n} , written log*  n {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 1 {displaystyle 1} . The simplest formal definition is the result of this recurrence relation: In computer science, the iterated logarithm of n {displaystyle n} , written log*  n {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 1 {displaystyle 1} . The simplest formal definition is the result of this recurrence relation: On the positive real numbers, the continuous super-logarithm (inverse tetration) is essentially equivalent: but on the negative real numbers, log-star is 0 {displaystyle 0} , whereas ⌈ slog e ( − x ) ⌉ = − 1 {displaystyle lceil { ext{slog}}_{e}(-x) ceil =-1} for positive x {displaystyle x} , so the two functions differ for negative arguments. The iterated logarithm accepts any positive real number and yields an integer. Graphically, it can be understood as the number of 'zig-zags' needed in Figure 1 to reach the interval [ 0 , 1 ] {displaystyle } on the x-axis. In computer science, lg* is often used to indicate the binary iterated logarithm, which iterates the binary logarithm (with base 2 {displaystyle 2} ) instead of the natural logarithm (with base e). Mathematically, the iterated logarithm is well-defined for any base greater than e 1 / e ≈ 1.444667 {displaystyle e^{1/e}approx 1.444667} , not only for base 2 {displaystyle 2} and base e. 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: The iterated logarithm grows at an extremely slow rate, much slower than the logarithm itself. 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. Higher bases give smaller iterated logarithms. Indeed, the only function commonly used in complexity theory that grows more slowly is the inverse Ackermann function.