110

What is O(log* N) and how is it different from O(log N)?

7
  • 2
    Is this question about the * after log or about O() notation in general? Commented Mar 5, 2010 at 15:09
  • 1
    It's in some advanced data structures, though I'm out of school for too long to recall where it comes from!
    – Larry
    Commented Mar 5, 2010 at 15:10
  • 2
    I guess not so advanced, just remembered - Union Find with path compression's initial lower bound was set at O(n log* n) until it was lowered to O(A n), where A is the inverse Ackermann function..
    – Larry
    Commented Mar 5, 2010 at 15:17
  • 1
    Heh. In practice, I think that I would be satisfied with an estimate of O(n) for that. :-) Commented Mar 5, 2010 at 15:48
  • 1
    This video is quite nice: youtube.com/watch?v=Z2vprYeJ0qs . It demonstrates that lg* follows exactly the same pattern like the normal functions lg, division, so it is not an artificial function even if it looks so. Commented Dec 19, 2015 at 18:20

3 Answers 3

105

O( log* N ) is "iterated logarithm":

In computer science, the iterated logarithm of n, written log* n (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1.

6
  • 12
    That is really interesting thing I'd not heard of. Q+A +1 each. I guess O(log*N) is for-all-intents-and-purposes O(1). Cool.
    – Greg
    Commented Mar 5, 2010 at 15:13
  • 1
    @greg, no log(n) means that as the number of elements goes up the time more slowly. eg. 10x as many elements only makes the function take 2x as long Commented Mar 5, 2010 at 15:18
  • 2
    I think I first came across it in the analysis of the Union-Find algorithm, when it was O( N log* N ) before it was improved to O( A N ), where A is the inverse Ackermann function. I still don't understand the latter proof, but the O( N log* N ) algorithm is a relatively good read.
    – Larry
    Commented Mar 5, 2010 at 15:19
  • 18
    @Martin, but this is log*(n) which goes up crazily slowly, such that log*(2^65536 -1) = 5. You might as well call that constant.
    – Greg
    Commented Mar 5, 2010 at 16:20
  • 5
    Sorry hadn't appreciated the log-star difference, thanks - learning something new! Commented Mar 5, 2010 at 17:32
34

The log* N bit is an iterated algorithm which grows very slowly, much slower than just log N. You basically just keep iteratively 'logging' the answer until it gets below one (E.g: log(log(log(...log(N)))), and the number of times you had to log() is the answer.

Anyway, this is a five-year old question on Stackoverflow, but no code?(!) Let's fix that - here's implementations for both the recursive and iterative functions (they both give the same result):

public double iteratedLogRecursive(double n, double b)
{
    if (n > 1.0) {
        return 1.0 + iteratedLogRecursive( Math.Log(n, b),b );
    }
    else return 0;
}

public int iteratedLogIterative(double n, double b)
{
    int count=0;
    while (n >= 1) {
        n = Math.Log(n,b);
        count++;
    }
    return count;
}
0
11

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.