patternMinor
Average case lower bound for sorting
Viewed 0 times
casesortingboundloweraveragefor
Problem
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?
Solution
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})$.
So the average case lower bound for sorting is $\Omega(n\lg{n})$.
Context
StackExchange Computer Science Q#41254, answer score: 2
Revisions (0)
No revisions yet.