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?

Answer 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!