[Solved]: Why is O(n log n) the best runtime there is?

Problem Detail: 

I am taking a course on Coursera about algorithm design. The course said that a time of $O(n \log n)$ is considered to be good.

However, there are faster runtimes such as (from now on just assume it is in big o notataion), such as $1$, $n$, and $\log n$. I understand that it is almost impossible to have a algorithm in $O(1)$ as that is for trivial tasks such as adding or multiplication.

However, why is there no algorithm in $O(\log n)$ time? Mergesort is considered to be a great algorithm and in its best and worst case scenario it is $O(n \log n)$ (I could be wrong). Why is merge sort considered to be a great algorithm when $O(n \log n)$ is only faster than $n^2$, $n!$, and $2^n$?

Also, why is there no sort with a time of $\log n$? This is not a homework question by the way, I am just purely curious as to why no sorting algorithm is in $\log n$ time.

Asked By : user1477539

Answered By : Raphael

Your confusion seems to stem from several misconceptions. I'll try to address some.

There are several ways an algorithm can be "best". Which is applicable depends on the context and on what you want to say.

• An algorithm is provably the best one, period. (Hint: impossible)
• An algorithm is the best we know. (Best in what metric?)
• An algorithm is provably optimal. (W.r.t. what metric? What about others? Proven under which assumptions?)
• An algorithm is probably asymptotically optimal. (W.r.t. what metric? What about others? Proven under which assumptions? What about the constant factor? What about small inputs?)

And probably more. Note that all these need an addition: "for problem P". Every algorithm solves some specific problem, and it does usually not make sense to compare algorithms for different problems.

Now, in the case of Mergesort, here are two facts.

• Mergesort takes $O(n \log n)$ operations to sort $n$ elements in the worst case.
• Sorting $n$ pairwise distinct elements (from an unknown range) by comparing element in a pairwise fashion requires $\Omega(n \log n)$ comparisons.

Hence, Mergesort is an asymptotically worst-case-optimal algorithm for sorting pairwise distinct numbers whose range is unknown (or huge), among all comparison-based sorting algorithms.

However:

• On average (again, model assumptions apply), Quicksort is faster Mergesort.
• For some input classes, there are linear-time sorting algorithms.
• On small inputs, even Insertion Sort is faster.

As you see, Mergesort is "best" in a certain sense, but not universally.

Regarding your specific question in the end, proving an $\Omega(n)$ lower bound for general sorting is easy. Try to imagine an algorithm that does not even look at every input element. Can it sort the input?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44076