algorithmmathcomplexity-theorylogarithmiterated-logarithm

What is O(log* N)?

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

Solution

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