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 .
 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
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!