6
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ It will take at least $n$ steps to inspect $n$ elements, so you can't have a sorting algorithm any faster than that. $\endgroup$
    – Rick Decker
    Jul 1, 2015 at 0:53
  • $\begingroup$ Ah that makes sense. So it is impossible to have a sorting algorithm be log(n), but what outside of sorting. I don't really understand how a n algorithm would be in log(n) time. $\endgroup$
    – user1477539
    Jul 1, 2015 at 0:58
  • $\begingroup$ Outside of sorting there are many algorithms that take time $O(\log n)$ on collections of $n$ objects. One example is binary search on a sorted list. Under certain assumptions, one can even do better than that, on average, as with interpolation search. In fact, there are even faster algorithms on collections of $n$ elements, like the ones on a union-find data structure. $\endgroup$
    – Rick Decker
    Jul 1, 2015 at 1:04
  • 1
    $\begingroup$ For sorting, see cs.stackexchange.com/questions/35164/… $\endgroup$
    – Pseudonym
    Jul 1, 2015 at 1:24
  • 1
    $\begingroup$ The running time of an algorithm can, in principle, be almost any non-decreasing function of $n$. So $n\log n$ is not "only faster than $n^2$, $n!$ and $2^n$." Your question is a bit like asking, "Why is 3 considered a really small number when it's only smaller than 7, 1082 and 491?" Whether or not 3 is really small depends a lot on the context you're working in and 3 isn't only smaller than 7, 1082 and 491: it's smaller than all of the infinitely many numbers bigger than 3. $\endgroup$
    – David Richerby
    Jul 1, 2015 at 5:56

1 Answer 1

Reset to default
8
$\begingroup$

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?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.