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?

Solution 1

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

So in general (log n)² 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)²)

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)² wins hands down:

Solution 2

For each constant k asymptotically log(n)^k < n.

Proof is simple, do log on both sides of the equation, and you get:

log(log(n))*k < log(n)

It is easy to see that asymptotically, this is correct.

---

Semantic note: Assuming here log(n)^k == log(n) * log(n) * ... * log(n) (k times) and NOT log(log(log(...log(n)))..) (k times) as it is sometimes also used.

Solution 3

O(n^2) vs. O(n*log(n)^2)
<=> O(n) vs. O(log(n)^2) (divide by n)
<=> O(sqrt(n)) vs. O(log(n)) (square root)
<=> polynomial vs. logarithmic

Logarithmic wins.

Comments

[amit]

log(100) < log(100)^2 (assuming ^2 means log(100)*log(100)), n==5 is a bad example.

[cHao]

Try with a million. log n = 13.8155... , and the square of it is 190.8683... . Keep in mind that O(some function of N) deals with large values of N.

[amit]

I believe the OP is after (log(n))^2 and not log(n^2)

[Yogendra Singh]

@amit I took even big number in the example. I was updating the answer already.

[Yogendra Singh]

@cHao I already took a bigger number which I think is good enough for example.

[Reza]

you are rigth: log(n(log(n)^2)=log(n)+log(log(n)^2)=log(n)+2(log(log(n))

[phant0m]

Notice how the green line shoots up to infinity for tiny values of n asymptotics is not about whether something goes to infinity, but about how fast it approaches infinity. log(n)^2 goes to infinity as well.

[Markus A.]

@phant0m What I was trying to point out is that (log n)^2 also goes to infinity for SMALL values of n, not just large ones. But that's more of a purely mathematical observation since n usually isn't less than 1 anyways... I'll get rid of the line. It doesn't really add anything useful...