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, 2015 at 16:22

1 Answer 1


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})$.

  • $\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$
    – Simd
    Apr 11, 2015 at 17:20
  • 1
    $\begingroup$ @Lembik This is average case analysis over uniform input distributions. $\endgroup$
    – orlp
    Apr 11, 2015 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$
    – Simd
    Apr 11, 2015 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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