Editing Iterated logarithm (section)

==Analysis of algorithms==
The iterated logarithm is useful in [[analysis of algorithms]] and [[computational complexity theory|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 [[Big-O notation|O]](''n''&nbsp;{{log-star}}&nbsp;''n'') time.<ref>{{cite journal
 | last = Devillers | first = Olivier
 | doi = 10.1142/S021819599200007X
 | journal = [[International Journal of Computational Geometry & Applications]]
 | volume = 2 | issue = 1
 | date = March 1992
 | pages = 97–111
 | mr = 1159844
 | title = Randomization yields simple <math>O(n\log^\ast n)</math> algorithms for difficult <math>\Omega(n)</math> problems
 | s2cid = 60203
 | arxiv = cs/9810007
 | url = https://inria.hal.science/file/index/docid/167206/filename/hal.pdf
 }}</ref>
* [[Fürer's algorithm]] for integer multiplication: O(''n''&nbsp;log&nbsp;''n''&nbsp;2<sup>''O''({{log-star|lg}}&nbsp;''n'')</sup>).
* Finding an approximate maximum (element at least as large as the median): {{log-star|lg}}&nbsp;''n'' − 1 ± 3 parallel operations.<ref>{{cite journal
 | last1 = Alon | first1 = Noga | author1-link = Noga Alon
 | last2 = Azar | first2 = Yossi
 | doi = 10.1137/0218017
 | journal = [[SIAM Journal on Computing]]
 | volume = 18 | issue = 2
 | date = April 1989
 | pages = 258–267
 | mr = 986665
 | title = Finding an approximate maximum
 | url = https://web.math.princeton.edu/~nalon/PDFS/Publications2/Finding%20an%20approximate%20maximum.pdf
 }}</ref>
* Richard Cole and [[Uzi Vishkin]]'s [[Graph coloring#Parallel and distributed algorithms|distributed algorithm for 3-coloring an ''n''-cycle]]: ''O''({{log-star}}&nbsp;''n'') synchronous communication rounds.<ref>{{cite journal
 | last1 = Cole | first1 = Richard | author1-link = Richard J. Cole
 | last2 = Vishkin | first2 = Uzi | author2-link = Uzi Vishkin
 | doi = 10.1016/S0019-9958(86)80023-7 | doi-access = free
 | journal = [[Information and Control]]
 | volume = 70 | issue = 1
 | pages = 32–53
 | mr = 853994
 | title = Deterministic coin tossing with applications to optimal parallel list ranking
 | date = July 1986
 | url = https://archive.org/download/deterministiccoi00vish/deterministiccoi00vish.pdf
 }}</ref>

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:

<math display="block">{^{y}b} = \underbrace{b^{b^{\cdot^{\cdot^{b}}}}}_y \gg \underbrace{b^{b^{\cdot^{\cdot^{b^{y}}}}}}_n</math>

the inverse grows much slower: <math>\log_b^* x \ll \log_b^n x</math>.

For all values of ''n'' relevant to counting the running times of algorithms implemented in practice (i.e., ''n''&nbsp;≤&nbsp;2<sup>65536</sup>, 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.

{|class=wikitable
|+The base-2 iterated logarithm
! ''x'' !! {{lg-star}}&nbsp;''x''
|-
| {{open-closed|−∞, 1}} || 0
|-
| {{open-closed|1, 2}} || 1
|-
| {{open-closed|2, 4}} || 2
|-
| {{open-closed|4, 16}} || 3
|-
| {{open-closed|16, 65536}} || 4
|-
| {{open-closed|65536, 2<sup>65536</sup>}} || 5
|}

Higher bases give smaller iterated logarithms.