107

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

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Timmy
  • 12,468
  • 20
  • 77
  • 107
  • Similar question: http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly No answer on `O(log* N)` unfortunately. – BalusC Mar 05 '10 at 15:08
  • 1
    Is this question about the * after log or about O() notation in general? – Bart van Heukelom Mar 05 '10 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 Mar 05 '10 at 15:10
  • http://stackoverflow.com/questions/111426/did-you-apply-computational-complexity-theory-in-real-life and http://stackoverflow.com/questions/107165/big-o-for-eight-year-olds covers this question – Pool Mar 05 '10 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 Mar 05 '10 at 15:17
  • 1
    Heh. In practice, I think that I would be satisfied with an estimate of O(n) for that. :-) – RBarryYoung Mar 05 '10 at 15:48
  • 1
    This video is quite nice: https://www.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. – ROMANIA_engineer Dec 19 '15 at 18:20

3 Answers3

101

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.

Larry
  • 4,491
  • 2
  • 24
  • 16
  • 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 Mar 05 '10 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 – Martin Beckett Mar 05 '10 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 Mar 05 '10 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 Mar 05 '10 at 16:20
  • 5
    Sorry hadn't appreciated the log-star difference, thanks - learning something new! – Martin Beckett Mar 05 '10 at 17:32
  • @MartinBeckett If you want, take `log*(x)=10`, or `2^2^2^2^2^2^2^2^2^2`, this is a number that if all the universe were full of electrons, I'm sure their number won't reach half of this number. Constant? mathematically, not, but practically, yes. – Chayim Friedman Jun 11 '20 at 23:15
33

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;
}
Dan W
  • 3,520
  • 7
  • 42
  • 69
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 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.