Course contentsShow
← Computer Science
Lesson 770 of 2,87218. Sorting AlgorithmsFree lesson

Average-Case Analysis: Expected Performance

Learn why quicksort achieves O(n log n) expected time complexity on random data despite worst-case behavior.

Average-Case Analysis: Expected Performance

What you'll learn: Why quicksort typically runs in O(n log n) time on random data, even though its worst case is O(n²).

The Paradox of Quicksort

You've seen that quicksort can be terrible (O(n²)) on already-sorted data when the pivot choices are bad. Yet quicksort is often the fastest sorting algorithm in practice. Why?

The answer lies in average-case analysis: examining performance on typical inputs, not just the worst possible scenario.

Why Random Data Saves Quicksort

When data is randomly arranged (or the pivot is chosen randomly), quicksort doesn't consistently pick terrible pivots. Instead:

  • Most partitions are reasonably balanced — not perfect 50/50 splits, but good enough
  • Even 25/75 splits lead to O(n log n) depth overall
  • The probability of repeatedly picking extremely bad pivots is vanishingly small

Think of flipping a coin multiple times: getting heads 10 times in a row is possible, but unlikely. Similarly, getting badly unbalanced partitions every single time is rare.

The Mathematical Insight

On random input, the expected recursion depth is O(log n) because:

  • Each partition operation still takes O(n) work at that level
  • But on average, the problem size shrinks by a consistent factor
  • This creates a recursion tree with logarithmic height

The math shows that the expected number of comparisons across all levels sums to O(n log n) — the same as mergesort's guaranteed performance!

Why This Matters

This explains quicksort's popularity: while worst-case is O(n²), randomly ordered data yields O(n log n) expected time. With good pivot selection (like random or median-of-three), you effectively guarantee average-case behavior in practice.

Key Takeaway: Quicksort achieves O(n log n) expected time complexity on random data because most pivot choices produce reasonably balanced partitions, making catastrophically bad splits extremely improbable.