English 中文(简体)
Big O Notation: differences between O(n^2) and O(n.log(n))?
原标题:
  • 时间:2009-12-03 21:44:57
  •  标签:
  • big-o

What is the difference between O(n^2) and O(n.log(n))?

最佳回答

n^2 grows in complexity more quickly.

问题回答

Big O calculates an upper limit of running time relative to the size of a data set (n).

An O(n*log(n)) is not always faster than a O(n^2) algorithm, but when considering the worst case it probably is. A O(n^2)-algorithm takes ~4 times longer when you duplicate the working set (worst case), for O(n*log(n))-algorithm it s less. The bigger your data set is the more it usually gets faster using an O(n*log(n))-algorithm.

EDIT: Thanks to harms , I ll correct a wrong statement in my first answer: I told that when considering the worst case O(n^2) would always be slower than O(n*log(n)), that s wrong since both are except for a constant factor!

Sample: Say we have the worst case and our data set has size 100.

  • O(n^2) --> 100*100 = 10000
  • O(n*log(n)) --> 100*2 = 200 (using log_10)

The problem is that both can be multiplied by a constant factor, say we multiply c to the latter one. The result will be:

  • O(n^2) --> 100*100 = 10000
  • O(n*log(n)) --> 100*2*c = 200*c (using log_10)

So for c > 50 we get O(n*log(n)) > O(n^2), for n=100.

I have to update my statement: For every problem, when considering the worst case, a O(n*log(n)) algorithm will be quicker than a O(n^2) algorithm for arbitrarily big data sets.

The reason is: The choice of c is arbitrary but constant. If you increase the data set large enough it will dominate the effect of every constant choice of c and when discussing two algorithms the cs for both are constant!

You ll need to be a bit more specific about what you are asking, but in this case O(n log(n)) is faster

Algorithms that run in O(nlog(n)) time are generally faster than those that run in O(n^2).

Big-O defines the upper-bound on performance. As the size of the data set grows (n) the length of time it takes to perform the task. You might be interested in the iTunes U algorithms course from MIT.

n log(n) grows significantly slower

"Big Oh" notation gives an estimated upper bound on the growth in the running time of an algorithm. If an algorithm is supposed to be O(n^2), in a naive way, it says that for n=1, it takes a max. time 1 units, for n=2 it takes max. time 4 units and so on. Similarly for O(n log(n)), it says the grown will be such that it obeys the upper bound of O(n log(n)). (If I am more than naive here, please correct me in a comment).

I hope that helps.





相关问题
Hamiltonian circuit

what is the Big-o complexity of finding a Hamiltonian circuit in a given order Markov chain using DFS?

Best practices for regex performance VS sheer iteration

I was wondering if there are any general guidelines for when to use regex VS "string".contains("anotherString") and/or other String API calls? While above given decision for .contains() is trivial (...

Worst case running time (Big O)

I have this question, and I don t know how to solve it, because I don t understand it. :( The question is: Programs A and B are analyzed and are found to have worst case running times no ...

How to add/merge several Big O s into one

If I have an algorithm which is comprised of (let s say) three sub-algorithms, all with different O() characteristics, e.g.: algorithm A: O(n) algorithm B: O(log(n)) algorithm C: O(n log(n)) How do ...

What s my Big O?

My program of sorting values clocks at: 100000 8s 1000000 82s 10000000 811s Is that O(n)?

热门标签