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

问题:

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?

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

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

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

回答4:

(Log n)^2 is better because if you do a variable change n by exp m, then m^2 is better than exp m

回答5:

(logn)^2 is also < n.

Take an example:

 n = 5
 log n = 0.6989....
 (log n)^ 2 = 0.4885..

You can see, (long n)^2 is further reduced.

Even if you take any bigger value of n e.g. 100,000,000 , then

   log n = 9
   (log n)^ 2 = 81

which is far less than n.

回答6:

O(n(logn)^2) is better (faster) for large n!

take log from both sides:

Log(n^2)=2log(n)

Log(n(logn)^2)=Log(n)+2log(Log(n))=Log(n)+2log(Log(n))

lim n--> infinity [(Log(n)+2log(Log(n)))/2log(n)/]=0.5 (use l'Hôpital's rule)(http://en.wikipedia.org/wiki/L'H%C3%B4pital's_rule)]