• Images
• Videos
• Documents
• Books
• Articles

Analysis of algorithms

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.³
• Fürer's algorithm for integer multiplication: O(n log n 2O(lg* n)).
• Finding an approximate maximum (element at least as large as the median): lg* n − 1 ± 3 parallel operations.⁴
• Richard Cole and Uzi Vishkin's distributed algorithm for 3-coloring an n-cycle: O(log* n) synchronous communication rounds.⁵

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:

y b = b b ⋅ ⋅ b ⏟ y ≫ b b ⋅ ⋅ b y ⏟ n {\displaystyle {^{y}b}=\underbrace {b^{b^{\cdot ^{\cdot ^{b}}}}} _{y}\gg \underbrace {b^{b^{\cdot ^{\cdot ^{b^{y}}}}}} _{n}}

the inverse grows much slower: log b ∗ ⁡ x ≪ log b n ⁡ x {\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 ≤ 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.

Other applications

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 O ( log ∗ ⁡ n ) {\displaystyle O(\log ^{*}n)} .

In computational complexity theory, Santhanam⁶ 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 n log ∗ ⁡ n . {\displaystyle n{\sqrt {\log ^{*}n}}.}

See also

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

References

1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. "The iterated logarithm function, in Section 3.2: Standard notations and common functions". Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 58–59. ISBN 0-262-03384-4. 0-262-03384-4 ↩

2. Furuya, Isamu; Kida, Takuya (2019). "Compaction of Church numerals". Algorithms. 12 (8) 159: 159. doi:10.3390/a12080159. MR 3998658. https://doi.org/10.3390%2Fa12080159 ↩

3. Devillers, Olivier (March 1992). "Randomization yields simple O ( n log ∗ ⁡ n ) {\displaystyle O(n\log ^{\ast }n)} algorithms for difficult Ω ( n ) {\displaystyle \Omega (n)} problems" (PDF). International Journal of Computational Geometry & Applications. 2 (1): 97–111. arXiv:cs/9810007. doi:10.1142/S021819599200007X. MR 1159844. S2CID 60203. https://inria.hal.science/file/index/docid/167206/filename/hal.pdf ↩

4. Alon, Noga; Azar, Yossi (April 1989). "Finding an approximate maximum" (PDF). SIAM Journal on Computing. 18 (2): 258–267. doi:10.1137/0218017. MR 0986665. /wiki/Noga_Alon ↩

5. Cole, Richard; Vishkin, Uzi (July 1986). "Deterministic coin tossing with applications to optimal parallel list ranking" (PDF). Information and Control. 70 (1): 32–53. doi:10.1016/S0019-9958(86)80023-7. MR 0853994. /wiki/Richard_J._Cole ↩

6. Santhanam, Rahul (2001). "On separators, segregators and time versus space" (PDF). Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001. IEEE Computer Society. pp. 286–294. doi:10.1109/CCC.2001.933895. ISBN 0-7695-1053-1. 0-7695-1053-1 ↩