Course contentsShow
← Computer Science
Lesson 825 of 2,87219. Searching and SelectionFree lesson

Median of Medians: Deterministic Selection

Introducing the median-of-medians algorithm that guarantees O(n) worst-case time for finding the k-th element.

Median of Medians: Deterministic Selection

What you'll learn: How the median-of-medians algorithm guarantees finding the k-th smallest element in O(n) time, even in the worst case.

The Problem with QuickSelect

You've seen that QuickSelect works great on average (O(n)), but with bad pivot choices it degrades to O(n²). What if you need a guarantee of O(n) performance every single time?

The Core Idea

The median-of-medians algorithm solves this by choosing a provably good pivot before partitioning. Here's how:

  1. Divide your array into groups of 5 elements each
  2. Find the median of each group (just 5 elements, so it's fast)
  3. Recursively find the median of all those medians
  4. Use that as your pivot for partitioning

Why does this work? The median-of-medians is guaranteed to be "good enough"—at least 30% of elements will be smaller and 30% larger. This prevents worst-case imbalance, ensuring each partition shrinks the problem significantly.

The Analogy

Imagine picking a team captain by first dividing everyone into small groups, choosing the middle person from each group, then picking the middle person from those representatives. You're guaranteed someone reasonably representative of the whole group—not the shortest or tallest person.

Complexity Reality Check

While theoretically O(n) in the worst case, the constant factors are larger than randomized QuickSelect. In practice, QuickSelect with random pivots is usually faster. But when you need guaranteed performance (real-time systems, safety-critical applications), median-of-medians delivers.

Key Takeaway: The median-of-medians algorithm uses a clever pivot selection strategy (median of group medians) to guarantee O(n) worst-case time for finding the k-th element, trading simplicity for deterministic performance.