The $\Omega(n\lg{n})$ lower bound for sorting in the comparison model is well known. Is there a similar average case lower bound for sorting in the comparison model and if so, which random distributions does it apply to?

  • $\begingroup$ You might want to look up Kolmogorov complexity, and more specifically average case analysis done with the incompressibility method. (It's a general proof method based on KC and random strings). $\endgroup$ – Juho Apr 11 '15 at 16:22

In the Sedgewick-Bentley talk "QUICKSORT IS OPTIMAL" they give an (informal) proof that Quicksorts average case is optimal.

So the average case lower bound for sorting is $\Omega(n\lg{n})$.

| cite | improve this answer | |
  • $\begingroup$ By average case I mean over random input distributions. I think you are referring to the average run time of a randomised algorithm which is something different. $\endgroup$ – Lembik Apr 11 '15 at 17:20
  • $\begingroup$ @Lembik This is average case analysis over uniform input distributions. $\endgroup$ – orlp Apr 11 '15 at 17:23
  • $\begingroup$ That's a very nice reference. Thank you. "The average number of compares per element C/N is always within a constant factor of the entropy H" $\endgroup$ – Lembik Apr 11 '15 at 17:28

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.