What is O(log* N)?
AlgorithmMathComplexity TheoryLogarithmIterated LogarithmAlgorithm Problem Overview
What is O(log* N) and how is it different from O(log N)?
Algorithm Solutions
Solution 1 - Algorithm
O( log* N ) is "http://en.wikipedia.org/wiki/Iterated_logarithm">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.
Solution 2 - Algorithm
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;
}
Solution 3 - Algorithm
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.