Quicksort's worst-case case cost is O(n^2) and its average-case cost is O(n \log n). This means that the fraction of input cases with cost O(n^2) must:

Drop as n grows
  • Never happen
  • Happen only once
  • Be less than half
  • Be less than 1 in n
  • Be less than 1 in n!

For any size n, it does happen that there are inputs that have cost n^2.

But if there were a constant fraction of such cases regardless of n, then the average would also be n^2.

So the fraction must be be dropping as n grows.