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

Question

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

Solution 1

Any function whose runtime has the form (log n)^k is O((log n)^k). This expression isn't reducable to any other primitive function using simple transformations, and it's fairly common to see algorithms with runtimes like O(n (log n)²). Functions with this growth rate are called polylogarithmic.

By the way, typically (log n)^k is written as log^k n, so the above algorithm would have runtime O(n log² n. In your case, the function log² n + log n would be O(log² n).

However, any function with runtime of the form log (n^k) has runtime O(log n), assuming that k is a constant. This is because log (n^k) = k log n using logarithm identities, and k log n is O(log n) because k is a constant. You should be careful not to blindly conclude that an algorithm that is O(log (n^k)) is O(log n), though; if k is a parameter to the function or depends on n, the correct big-O computation would be O(k log n) in this case.

Depending on the context in which you're working, you sometimes see the notation Õ(f(n)) to mean O(f(n) log^k n) for some constant k. This is sometimes called "soft-O" and is used in contexts in which the logarithmic terms are irrelevant. In that case, you could say that both functions are Õ(1), though this usage is not common in simple algorithmic analysis (in fact, outside of Wikipedia, I have seen this used precisely once).

Hope this helps!

Solution 2

It will still be (log(n))^2. A logarithm raised to a power is already in the lowest/simplest form.

Solution 3

(log n)^k is:

• O((log n)^k)
• O(n^k)
• O(n)
• O(n log n)
• O(n^1/2)
• O(n^0.00000002)

etc. Which one is meaningful for you depends on the constants and the context.

Solution 4

log(n) is O((log(n))^2) so the entire expression is O((log(n))^2)

View more solutions

Comments

[Foo Bah]

one note on notation: you should be careful when writing log^k n because many randomized algorithms have complexities with terms like log(log(n)) or log(log(log(n))), and in some circles (e.g. in operations research), authors use log^k(n) to refer to repeated applications of logarithms.

[templatetypedef]

@Foo Bah- That's an excellent point. The notation log^* is also weird this way.

[ypercubeᵀᴹ]

Yeah, but it's only Θ((log n)^k)

[Alexandre C.]

@ypercube: the OP didn't ask for big-theta.

[ypercubeᵀᴹ]

Yes, technically your answer is correct. I guess that's why you have +1

[Neowizard]

What do you think that log(n) is O((log(n))^2)?

[Admin]

@ypercube: it's also Θ((log n)^k + 1)