Median of Medians: Complexity Proof
You'll learn how to mathematically prove that Median of Medians achieves guaranteed linear time for selection.
Why We Need the Proof
The Median of Medians algorithm claims O(n) worst-case time, unlike QuickSelect's O(n²). But how do we know this? We need to analyze its recurrence relation and prove it mathematically.
The Recurrence Relation
Recall that Median of Medians:
- Divides n elements into groups of 5: O(n)
- Finds median of each group: O(n)
- Recursively finds the median of those medians: T(n/5)
- Partitions around that pivot: O(n)
- Recursively searches one side: T(≤ 7n/10)
This gives us:
T(n) ≤ T(n/5) + T(7n/10) + O(n)
The key insight: at least 3n/10 elements are guaranteed eliminated after partitioning, so the worst recursive call processes at most 7n/10 elements.
Proving Linear Time by Induction
Claim: T(n) ≤ cn for some constant c.
Base case: For small n, T(n) = O(1).
Inductive step: Assume T(k) ≤ ck for all k < n. Then:
T(n) ≤ c(n/5) + c(7n/10) + dn
= cn/5 + 7cn/10 + dn
= 9cn/10 + dn
For T(n) ≤ cn, we need: 9cn/10 + dn ≤ cn
This simplifies to: dn ≤ cn/10, or c ≥ 10d.
Choosing c = 10d makes it work! The fractions n/5 and 7n/10 sum to 9n/10 < n, leaving room for the linear work.
Key Takeaway: The Median of Medians recurrence T(n) ≤ T(n/5) + T(7n/10) + O(n) provably solves to O(n) because the recursive subproblems shrink fast enough (9n/10 total) to absorb the linear partitioning cost, proven rigorously via mathematical induction.