Iterated logarithm

From CryptoDox, The Online Encyclopedia on Cryptography and Information Security

In computer science, the iterated logarithm of n, written log^*n (usually called "log star" in conversation), 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 recursive function:

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

or, in pseudocode:

function iterLog(real n)
    if n ≤ 1
        return 0
    else
        return 1 + iterLog(log(n))

Image:Iterated logarithm.png

Figure 1. Demonstrating lg^*4 = 2

In computer science, lg^* is often used to indicate the binary iterated logarithm, which iterates the binary logarithm instead. The iterated logarithm accepts any positive real number and yields a natural number. Graphically, it can be understood as the number of "zig-zags" needed in Figure 1 to reach the interval [0, 1] on the x-axis.

Mathematically, the iterated logarithm is well-defined not only for base 2 and base e, but for any base greater than $e^{1/e}\approx1.444667$ .

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

Finding the Delaunay triangulation of a set of points knowing the Euclidean minimum spanning tree: randomized O(n log^*n) time, Olivier Devillers
The disjoint set data structure's union and find operations: O(log^*n) time
Fürer multiplication: O(n log n 2^{lg* n})

The iterated logarithm is an extremely slowly-growing function, much more slowly than the logarithm itself; for all practical values of n (less than 2⁶⁵⁵³⁶, which is much more than the number of atoms in the observed universe), it does not exceed 5. Indeed, the only function used in complexity theory that grows more slowly is the inverse of the Ackermann function. For all practical purposes, the iterated logarithm may be considered to be a constant.

References

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 55–56 of section 3.2.

Navigation

Iterated logarithm

From CryptoDox, The Online Encyclopedia on Cryptography and Information Security

References

See also