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.
