What is O(log* N)? I found it online with no description.
edit: I know big-Oh, the log* was the question
views:
831answers:
3
+40
A:
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
2010-03-05 15:08:07
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
2010-03-05 15:13:53
@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
2010-03-05 15:18:45
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
2010-03-05 15:19:11
@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
2010-03-05 16:20:06
Sorry hadn't appreciated the log-star difference, thanks - learning something new!
Martin Beckett
2010-03-05 17:32:39
A:
It indicates how an algorithm performs: Big O Notation (scroll down to "Orders of common functions" and you will see a lot of samples, including yours)
Stefan Egli
2010-03-05 15:10:25