 # Iterated Logarithm Function

Share on

The iterated logarithm functionlog * n (“log star of n”) is defined as the smallest natural number k for which
log(i) ≤ 1.
The function is not defined for n < 1.

Formally, it is defined as :

• log * n = 0 if n ≤ 1
• log * n = 1 + log * (log n) if n > 1.

This slow growing function measures how many times you have to take the logarithm of n before it drops to one  or how many times you can take the log n base of a number .

A few examples:

• log * 1 = 0
• log * 2 = 1
• log * 4 = 2
• log * 16 = 3
• log * 65,536 = 4.
• log * (265536) = 5

This function is very slow-growing. Since the number of atoms in the universe if about 1080, which is a lot less than 265536, it’s very rare to see any use the iterated logarithm function for numbers that high: lg * 1020 exceeds the number of bytes in all of the computers on the planet .

Uses include algorithm analysis and building search trees (the Union-Find algorithm) in computer science, probability theory , mathematical systems and control theory , as well as various mathematical areas like the study of sets in bounded systems.

## Iterated Logarithm Function & Tower-of-2

The iterated logarithm function is the inverse of the tower-of-2 function (similar to how log2x is the inverse of 2x). The first few towers-of-2:

• tower-of-2(1) = 2
• tower-of-2(2) = 22 = 4
• tower-of-2(3) = 16
• tower-of-2(4) = 65,536
• tower-of-2(5) ≈ 10006,553

As this is the inverse of the iterated logarithm function, it grows very slowly. If you’re trying to calculate log * n by hand, it’s often much easier to calculate tower-of-2 first, then compare the number in question to see which “bucket” it falls into .

## References

 600.363 Introduction to Algorithms / 600.463 Algorithms I
 Problem Set 1: RMQ.
 Disjoint Set Data Structure.
 Eichelsbacher, P. & Lowe, M. Workshop on Probability Theory and Its Applications. Retrieved July 31, 2021 from: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.7719&rep=rep1&type=pdf
 Blondel, V. & Megretski, A. [Eds.]. Unsolved Problems in Mathematical Systems and Control Theory. Retrieved July 31, 2021 from: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.134.1462&rep=rep1&type=pdf
 Elkins, D. (2017). Computing the Iterated Logarithm (log-star) by hand. Retrieved July 31, 2021 from: https://math.stackexchange.com/questions/2553258/computing-the-iterated-logarithm-log-star-by-hand

CITE THIS AS:
Stephanie Glen. "Iterated Logarithm Function" From CalculusHowTo.com: Calculus for the rest of us! https://www.calculushowto.com/iterated-logarithm-function/
------------------------------------------------------------------------------

Need help with a homework or test question? With Chegg Study, you can get step-by-step solutions to your questions from an expert in the field. Your first 30 minutes with a Chegg tutor is free!