What does "log*" mean?

Question

I have come across the term O(log* N) in a book I'm reading on data structures. What does log* mean? I cannot find it on Google, and WolframAlpha doesn't understand it either.

Answer 1

It's iterated logarithm. See here for a description of lots of different time complexities, and here for more details on the iterated logarithm itself.

The iterated logarithm is the number of times the logarithm has to be applied before the result becomes one or less.

Answer 2

It's called iterated logarithm function. It is a very slowly growing function. For example:

• lg*(2) = 1
• lg*(4) = 2
• lg*(16) = 3
• lg*(65536) = 4
• lg*(2^65536) = 5 /note that (2^65536) is much larger than the number of atoms in the observable universe/

Or in the case of Big O it could pretty much be considered as constant time.