Iterated logarithm

The iterated logarithm \(\log^* x\) is defined as the number of iterations of \(\log x\) needed to reach a number less than 1. Formally:
# If \(x \leq 1\), \(\log^* x = 0\).
# Else, \(\log^* x = \log^* (\log x) + 1\).
It is used in computational complexity theory: there are algorithms known to have time complexity \(O(\log^* n)\). However, \(\log^*\) is so slow-growing that such algorithms practically run in constant time.
Category:Functions