The iterated logarithm, or log-star function, counts the number of repeated applications of a logarithm needed to obtain a value at most 1.
For a fixed base 
, it can be defined recursively by
 |
(1)
|
For example, 
,
since 
.
The function grows extremely slowly. Changing the fixed base
changes its value by at most an additive constant in
the asymptotic settings where it occurs.
In the analysis of algorithms, the iterated logarithm is distinct from a 
-fold
nested logarithm: 
returns the required number of iterations,
whereas a nested logarithm with fixed depth 
returns the value after exactly 
iterations.
