Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What does it mean to say that

heap sort and merge sort are asymptotically optimal comparison sorts .

I know What the Big O , Big Omega($\omega)$ and Theta($\theta$) notations are and I also know why these two sorts are called comparison sorts ? But I am not able to understand why they are called asymptotically optimal ? Why doesn't this asymptotically optimal property also apply to quick sort ?

P.S: I had a look in this question but still I am not clear about the definition of asymptotically optimal .

share|improve this question
    
Because the Landau symbols only give you asymptotic statements, that is in the limit for $n \to \infty$. –  Raphael Aug 12 '12 at 8:56
add comment

3 Answers

up vote 3 down vote accepted

Computing a simple function that characterizes the behavior of an algorithm for any input is difficult. So upper and lower bounds are used, in addition to probabilistic methods.

The term 'asymptotic' is used because the bound is typically only valid for large $n$, as an accurate formula for small $n$ is more complicated, and not really interesting from a performance perspective.

To answer your question, you can prove that any working comparison sort takes a lower bound of $\Omega(n \lg n)$ on running time. Consequently, if you can show that a sorting algorithm (such as heapsort or merge sort) has an upper bound of $O(n \lg n)$ on running time, then in fact you have a running time of $\Theta(n \lg n)$ which is, by definition, an asymptotically tight bound for the running time (See Cormen, Leiserson & Rivest's "Introduction to Algorithms", Chapter 2, Theorem 2.1, and the section on sorting).

Quicksort has a worst-case running time of $\Theta(n^2)$, which is larger than the above bound, hence is not optimal.

Note, however, that quicksort has an average running time of $\Theta(n \lg n)$. (This, of course, assumes that all inputs of length $n$ are equally likely.)

share|improve this answer
    
I also have a related question here . I got an answer still not clear on it yet . Can you answer that ? –  Geek Aug 11 '12 at 19:36
    
I added a comment to the question. In short, I don't have a good answer. –  copper.hat Aug 11 '12 at 19:56
add comment

It means that they can't be improved upon. It's fairly easy to prove that any comparison sort can't do better than $\Theta(n \log n)$, so any comparison sort which achieves $\Theta(n \log n)$ is asymptotically optimal.

Quick sort is $O(n^2)$ and that bound can't be tightened.

share|improve this answer
    
isn't quick sort also $O(n \log n)$ on average ? Its worst case if it is run without any randomization is $O(n^2)$ though. –  Geek Aug 11 '12 at 19:07
    
"Quick sort is O(n2) and that bound can't be tightened." I think you meant that that bound can be tightened further meaning can be improved upon or am I missing something fundamental here ? –  Geek Aug 11 '12 at 19:17
    
@Geek, depends on what you average over. And worst case is what's relevant unless otherwise specified. –  Peter Taylor Aug 11 '12 at 19:49
add comment

It means the following: Let $A$ be a comparison based sorting algorithm, and denote $T_{A}(n$) the time complexity of $A$ then $T_{A}(n)=\Omega(nlogn)$

That is, there exist a constant $c>0$ and $n_{0}$ such that for every $n>n_{0}$ it holds that $T_{A}(n)\geq c\cdot nlogn$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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