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

Answer 2

log* is the number of times you need to apply the log-function until you reach a value which less or equal to 1. For Instance: log*(16) = 3, because log₂(log₂(log₂(16))) = 1.

For practical purposes you can treat it like a constant, because this function grows very slow.

Answer 3

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 4

log* (n)- "log Star n" as known as "Iterated logarithm"

In simple word you can assume log* (n)= log(log(log(.....(log* (n))))

log* (n) is very powerful.

Example:

1) Log* (n)=5 where n= Number of atom in universe

2) Tree Coloring using 3 colors can be done in log*(n) while coloring Tree 2 colors are enough but complexity will be O(n) then.

3) Finding the Delaunay triangulation of a set of points knowing the Euclidean minimum spanning tree: randomized O(n log* n) time.

I hope you can Visualize Log* (n) like this on WolframAlpha Check here