O(n^2) vs O (n(logn)^2)

Question

Is time complexity `O(n^2)` or `O (n(logn)^2)` better? I know that when we simplify it, it becomes ``` O(n) vs O((logn)^2) ``` and `logn` < `n`, but what about `logn^2`?

Accepted Answer

n is only less than (log n)2 for values of n less than 0.49...

So in general (log n)2 is better for large n...

But since these O(something)-notations always leave out constant factors, in your case it might not be possible to say for sure which algorithm is better...

Here's a graph:

(The blue line is n and the green line is (log n)2)

Notice, how the difference for small values of n isn't so big and might easily be dwarfed by the constant factors not included in the Big-O notation.

But for large n, (log n)2 wins hands down:

O(n^2) vs O (n(logn)^2)

Solution

Problem