Selection and closest pair

Overview

Kent Quanrud develops two divide-and-conquer algorithms: deterministic linear-time selection using the median-of-medians pivot, and an O(n log n) algorithm for the closest pair of planar points. The selection analysis contrasts useful multiplicative shrinkage with ineffective additive progress, then proves that groups of five produce a pivot leaving at most about 70% of the input; the closest-pair analysis uses a narrow strip and a packing argument to limit comparisons to a constant number per point.

Key takeaways

For general rank-K selection, retaining the K smallest values in a max-heap costs O(n log K); it matches sorting's O(n log n) scale when K is Θ(n).
A linear-time approximate pivot is sufficient for exact selection when every partition removes a constant fraction: T(n) = T(0.9n) + O(n) is O(n).
Removing only a fixed number of elements per pass leads to quadratic work: T(n) = T(n-2) + O(n) sums to Θ(n²).
Median-of-medians groups n values into fives, recursively selects the median of the group medians, and guarantees roughly 30% of values on each side; T(n) = T(n/5) + T(7n/10) + O(n) is linear.
For planar closest pair, after recursively finding distance δ on each side of a median-x split, only points in a width-2δ strip can improve the answer.
A geometric packing argument shows that only a constant number of y-ordered strip points need comparison per point, yielding T(n) = 2T(n/2) + O(n) = O(n log n).

Chapters

0:00 Selection: Finding the Rank-K Element

Selection returns the Kth-smallest value from an array of comparable elements; the median is the special case near rank n/2.
For the lecture's example, 56 is the median because five listed values are smaller and five are larger.
The goal is to find a requested rank without fully sorting all n elements.

0:26 Sorting and Heaps as Selection Baselines

Sorting takes O(n log n), after which the rank-K answer is available at its indexed position.
For K < n/2, a max-heap of the K smallest values makes it efficient to identify and replace the largest retained value.
Processing n elements with O(log K) heap updates costs O(n log K), which becomes O(n log n) when K is proportional to n.
A balanced search tree also needs O(log n) per insertion, so incremental ordering does not improve the general bound.

5:23 Why Selection Needs a Carefully Chosen Pivot

Keeping only a running median can discard values that later become important as the input continues to arrive.
Reordering the same values can change the behavior of order-sensitive strategies even though the answer is unchanged.
A recursive selection method needs a pivot that separates the input into smaller and larger values and substantially reduces the relevant subproblem.

10:02 An Exact-Median Oracle Would Give Linear Selection

If a linear-time routine returned the exact median, a scan could partition the array and recursion would continue on at most n/2 elements.
The recurrence T(n) = T(n/2) + O(n) sums to O(n), since successive levels process n, n/2, n/4, and so on.
The difficulty is that computing an exact median is itself a selection problem, so the hypothetical oracle does not solve the implementation problem.

18:48 Approximate Medians and Geometric Shrinkage

A pivot guaranteed to lie in the middle 80% of the input leaves at most 90% of the elements on the side containing the desired rank.
Partitioning takes O(n), giving T(n) = T(0.9n) + O(n) in the worst case.
The total work is a decreasing geometric series, so even a pivot much less balanced than the exact median still yields O(n) time.

30:07 Why Removing Only a Few Extreme Values Fails

Finding the minimum and maximum removes only two elements, leading to T(n) = T(n-2) + O(n).
Unrolling this recurrence sums work close to n + (n-2) + (n-4) + …, which is Θ(n²).
The essential requirement is multiplicative shrinkage, such as removing a constant fraction—not merely an additive number—of elements.

41:20 Why a Small Sample Median Can Still Be Too Slow

Taking the median of a sample of n/10 elements guarantees only about n/20 values on either side of that sample median.
The main recursive call may therefore still have size about 19n/20, while another recursive call computes the sample's median.
The two-branch recurrence can make total work grow across recursion-tree levels; this sampling scheme does not establish a linear-time bound.
A random pivot can work well in practice, but this discussion restricts attention to deterministic guarantees.

51:09 Median of Medians: Build a Robust Pivot from Groups of Five

Partition the input into groups of five and find each group's median using constant work per group, for O(n) total work.
Recursively select the median of those group medians to use as the pivot for the original array.
This deterministic construction avoids relying on a randomly favorable pivot or on a sample chosen from fixed array positions.

55:26 Groups of Five Guarantee a 30%-70% Pivot Split

Order the group medians conceptually; at least half lie on either side of the median of medians.
For each such group, its median and the two values on the same side are also on that side of the pivot, giving roughly 3n/10 values below and 3n/10 above.
Allowing for incomplete groups and small additive terms, the larger selection subproblem has size at most about 7n/10.
The recurrence T(n) = T(n/5) + T(7n/10) + O(n) is linear because the recursive fractions sum to 0.9.

1:00:13 Closest Pair: From Quadratic Search to Divide and Conquer

Checking every pair among n planar points takes Θ(n²) time.
In one dimension, sorting the coordinates and checking neighboring points finds the closest pair in O(n log n).
A divide-and-conquer approach splits points into two halves, finds each half's closest distance recursively, then checks pairs crossing the split.

1:03:19 Split Planar Points by the Median X-Coordinate

Use selection to find a median x-coordinate and divide the points into left and right subsets.
Let δ be the smaller of the closest-pair distances found recursively on the two sides.
Any improving cross-boundary pair must lie within distance δ of the dividing line, so only a vertical strip around the split needs further examination.

1:05:10 Use Y-Order to Bound Strip Comparisons

Keep the points ordered by y-coordinate so the strip can be scanned from top to bottom without sorting again at every recursive level.
A point need only be compared with a constant number of subsequent strip points; the lecture uses a bound such as the next 10.
Points on the same side are already separated by at least δ, which prevents an arbitrarily dense cluster of viable cross-boundary candidates.

1:09:00 Packing Argument Limits Nearby Points

Within a region of dimensions on the order of δ by δ, points on either recursive side must be at least δ apart.
Around each point, draw a disk of radius δ/2: the disks are disjoint and fit inside a slightly enlarged square.
Comparing the disks' total area with the enlarged square's area bounds the number of points in the region by a constant.

1:11:55 Closest-Pair Recurrence and O(n log n) Bound

The two recursive calls each handle n/2 points, while finding the median split and scanning the strip costs O(n).
The recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n), improving on the Θ(n²) all-pairs method.
The next lecture topic is fast multiplication of two n-bit integers.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Kent Quanrud.