What is O(log* N)?

algorithm math complexity-theory logarithm iterated-logarithm
Timmy picture Timmy · Mar 5, 2010 · Viewed 34.7k times · Source

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

Answer

Larry picture Larry · Mar 5, 2010

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.

Related questions

What is the big-O of the function (log n)^k

What is the big-O complexity of the function (log n)k for any k?

Read More
What is the complexity of the log function?

What is the complexity of the log base 10 function?

Read More
Is log(n!) = Θ(n·log(n))?

I am to show that log(n!) = Θ(n·log(n)). A hint was given that I should show the upper bound with nn and show the lower bound with (n/2)(n/2). This does not seem all that intuitive to me. …

Read More