What is the big-O of the function (log n)^2 + logn

问题:

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

回答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!

回答2:

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

回答3:

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

回答4:

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