Chapter 6: Medians and Order Statistics

Source files used: Medians_induction (Lecture 2 notes, pages 8 to 10), Matrix Multiplication (Recitation 1, Section 3.3); textbook Chapter 9 (chap9) as support. No worked examples are included.

1. Big Picture

Median finding is the lecture’s second divide-and-conquer example: find the element of a given rank without sorting.

The Convex Hull guide split the input into two equal halves. This guide splits around a pivot, recurses on only one side, and needs a clever pivot so that side is never too big.

\boxed{\text{Pick a good pivot (median of medians), recurse on one side}\Rightarrow\Theta(n)\text{ worst case.}}

New ideas:

rank and order statistics,
the generic Select $(S,i)$ skeleton,
columns of 5 and the median of medians,
an unequal recurrence solved by induction, not the master theorem,
textbook context: min/max, randomized select.

2. Core Ideas

2.1 Rank and Medians

Given a set of $n$ numbers, the lectures define

$\text{rank}(x)$ = number of elements in the set that are $\le x$ .

The $i$ th order statistic is the element of rank $i$ . Rank 1 is the minimum, rank $n$ the maximum.

\text{lower median: rank }\left\lfloor\frac{n+1}{2}\right\rfloor,\qquad\text{upper median: rank }\left\lceil\frac{n+1}{2}\right\rceil

For odd $n$ they coincide. The textbook says “the median” to mean the lower median.

2.2 Sorting Is Too Slow

Sorting and indexing works in $\Theta(n\lg n)$ . Selection can be done in $\Theta(n)$ , so it beats the $\Omega(n\lg n)$ comparison-sorting lower bound by never fully sorting.

2.3 The Select Skeleton

Select $(S,i)$ :

Pick $x\in S$ (cleverly).
Compute $k=\text{rank}(x)$ , and split into $B=\{y\in S\mid y<x\}$ ( $k-1$ elements) and $C=\{y\in S\mid y>x\}$ ( $n-k$ elements).
If $k=i$ , return $x$ . If $k>i$ , return Select $(B,i)$ . If $k<i$ , return Select $(C,i-k)$ .

Watch the rank shift: in $C$ you look for rank $i-k$ , not $i$ .

2.4 Why the Pivot Must Be Good

If $\text{rank}(x)$ is extreme (near 1 or $n$ ), each call removes only a few elements, and the time becomes $T(n-1)+\Theta(n)=\Theta(n^2)$ . The lectures need $x$ so that $\text{rank}(x)$ is not extreme, guaranteeing a constant fraction is discarded every time.

2.5 Median of Medians

Arrange $S$ into columns of size 5 ( $\lceil n/5\rceil$ columns).
Sort each column, big elements on top (linear time: each column is constant size).
Find the median of the column medians recursively; that is $x$ .

Columns whose median is larger than $x$ contribute their median and the two elements above it, all $>x$ . Columns whose median is smaller contribute three elements $<x$ .

3. Main Governing Equations and Formulas

3.1 Guaranteed Elements on Each Side

Half of the $\lceil n/5\rceil$ groups contribute at least 3 elements greater than $x$ , except the one group with fewer than 5 elements and the group containing $x$ itself:

\#\{y>x\}\ge3\left(\left\lceil\frac{n}{10}\right\rceil-2\right)\ge\frac{3n}{10}-6

The same bound holds for elements less than $x$ . So the recursive call in step 3 is on at most

n-\left(\frac{3n}{10}-6\right)=\frac{7n}{10}+6\text{ elements}

Use to justify the $7n/10+6$ term in the recurrence.

3.2 Select Recurrence (Lecture)

T(n)=\begin{cases}O(1) & n\le140\\[4pt] T\!\left(\left\lceil n/5\right\rceil\right)+T\!\left(\dfrac{7n}{10}+6\right)+\Theta(n) & n>140\end{cases}

where:

$T(\lceil n/5\rceil)$ : finding the median of medians,
$T(7n/10+6)$ : recursing on the side that is kept (after discarding at least $3n/10-6$ ),
$\Theta(n)$ : sorting columns and partitioning.

The master theorem does not apply (two different subproblem sizes).

3.3 Intuition for Linear Time

\frac{n}{5}+\frac{7n}{10}=\frac{9n}{10}<n

The total input size of the subproblems shrinks by a constant factor each level, so the level costs form a decreasing geometric series dominated by the root’s $\Theta(n)$ .

3.4 Proof $T(n)\le cn$ by Induction (Lecture)

Let $an$ cover the $\Theta(n)$ term. True for $n\le140$ by choosing $c$ large. Inductive step:

T(n)\le c\left\lceil\frac{n}{5}\right\rceil+c\left(\frac{7n}{10}+6\right)+an

\le\frac{cn}{5}+c+\frac{7nc}{10}+6c+an

=cn+\left(-\frac{cn}{10}+7c+an\right)

Done if the bracket is $\le0$ , which means

c\ge\frac{70c}{n}+10a

This holds for $n\ge140$ and $c\ge20a$ (at $n\ge140$ , $70c/n\le c/2$ ).

Use this exact proof on exams. It explains why the base case is $n\le140$ .

3.5 Proof Variant (Recitation)

The recitation proves $T(n)\le dn$ with $cn$ as the linear term:

T(n)\le d\left(\frac{n}{5}+1\right)+d\left(\frac{7n}{10}+6\right)+cn=\frac{9}{10}dn+7d+cn\le dn

The last step holds for large enough $n$ when $d>10c$ .

3.6 Minimum and Maximum (Textbook)

Minimum alone: $n-1$ comparisons, and this is optimal (every non-winner must lose once).
Minimum and maximum together: at most $3\lfloor n/2\rfloor$ comparisons, by processing elements in pairs (compare the pair, then smaller vs current min and larger vs current max).

3.7 Randomized Select (Textbook)

Partition around a random pivot, recurse on one side.

\text{expected time }\Theta(n),\qquad\text{worst case }T(n)=T(n-1)+\Theta(n)=\Theta(n^2)

A partitioning is “helpful” (keeps at most $3/4$ of the elements) with probability at least $1/2$ , so on average it takes about two tries per helpful step. The expected number of comparisons is less than $8n$ .

This is the practical choice; the textbook calls the median-of-medians Select mostly of theoretical interest.

4. Problem-Solving Workflow

4.1 Describing Select

Define $\text{rank}(x)$ and the target rank $i$ .
Split into columns of 5, sort each column, take the column medians.
Recursively select the median of medians as pivot $x$ .
Partition into $B$ (less than $x$ ) and $C$ (greater than $x$ ), compute $k=\text{rank}(x)$ .
Return $x$ , recurse on $B$ with $i$ , or recurse on $C$ with $i-k$ .

4.2 Analyzing Select

Count elements guaranteed on each side: at least $3n/10-6$ (Section 3.1).
Write $T(n)=T(\lceil n/5\rceil)+T(7n/10+6)+\Theta(n)$ .
Note the master theorem does not apply.
Guess $O(n)$ from $n/5+7n/10<n$ .
Prove $T(n)\le cn$ by induction with explicit constants (Section 3.4).
Conclude $\Theta(n)$ (the column sorting alone is $\Omega(n)$ ).

5. Decision Rules / Decision Trees

5.1 Which Side to Recurse On?

$k=i$ ? → return $x$

$k>i$ ? → Select $(B,i)$

$k<i$ ? → Select $(C,i-k)$

5.2 Which Selection Algorithm?

Need a worst-case linear guarantee? → median of medians Select, $\Theta(n)$

Need a fast, simple method in practice? → randomized select, expected $\Theta(n)$ , worst $\Theta(n^2)$

Need only min or max? → single scan, $n-1$ comparisons

Need both min and max? → pairs trick, $3\lfloor n/2\rfloor$ comparisons

5.3 Proving the Recurrence

Recurrence has two different subproblem sizes? → no master theorem: substitution (induction)

Proof does not close? → check the constants: need $c\ge20a$ and the right base range ( $n\le140$ )

6. Important Tables / Correlations Needed

6.1 Selection Algorithms

Algorithm	Pivot	Worst case	Expected
Sort then index	none	$\Theta(n\lg n)$	$\Theta(n\lg n)$
Randomized select	random	$\Theta(n^2)$	$\Theta(n)$
Select (median of medians)	median of column medians	$\Theta(n)$	$\Theta(n)$

6.2 Median-of-Medians Numbers

Quantity	Value
Column size	5
Number of columns	$\lceil n/5\rceil$
Elements guaranteed $>x$ (and $<x$ )	$\ge3(\lceil n/10\rceil-2)\ge3n/10-6$
Largest recursive call	$7n/10+6$
Base case in the lecture proof	$n\le140$
Constant condition	$c\ge20a$

7. Key Takeaways

$\text{rank}(x)$ = number of elements $\le x$ ; lower median has rank $\lfloor(n+1)/2\rfloor$ .
Selection runs in $\Theta(n)$ , faster than sorting.
Select skeleton: pivot, partition into $B$ and $C$ , recurse on one side; use $i-k$ in $C$ .
A bad pivot gives $T(n-1)+\Theta(n)=\Theta(n^2)$ .
Median of medians with columns of 5 guarantees at least $3n/10-6$ elements on each side.
Recurrence: $T(\lceil n/5\rceil)+T(7n/10+6)+\Theta(n)$ , with $O(1)$ for $n\le140$ .
The master theorem does not apply; prove $T(n)\le cn$ by induction.
The proof closes for $n\ge140$ and $c\ge20a$ .
Intuition: $n/5+7n/10<n$ .
Randomized select: expected $\Theta(n)$ , worst case $\Theta(n^2)$ .