Unit 4.2 · about 5 h
114 / 324Divide and conquer, recurrences and partition-based selection
Divide and conquer sets the price of every recursive algorithm you will write. Selection shows the same recurrence idea deciding between linear and quadratic time.
- derive
- implement
You can now
- Solve \(T(n) = 2T(n/2) + n\), \(T(n) = T(n/2) + n\), and \(T(n) = T(n-1) + 1\) with recursion trees, stating depth, per-level cost and leaf count.
- Explain why floors and ceilings change the answer by at most a constant factor, and when an unbalanced split breaks the tree bound.
- Implement deterministic linear-time selection by median of medians and check it against a sorted oracle with pytest on small shuffled inputs.
- State the quickselect recurrence and its quadratic worst case, and point to the partition unit for the invariant and to the randomized unit for the expected cost.
Covers
- Divide, solve and combine structure
- Recursion trees and common cost recurrences
- Partition-based selection and pivot behavior
Study, in this order
2 steps
- Recursion, Chapter 1Algorithms - recursion, backtracking and greedy
1.4 Mergesort, 1.5 Quicksort, 1.6 The Pattern and 1.7 Recursion Trees (printed pp. 26-35), then 1.8 Linear-Time Selection: Quickselect, Good pivots and Analysis (printed pp. 35-40)
Depth · Skip Fast Multiplication and Exponentiation here. They return with dynamic programming and number theory.
- Recursion patterns: linear, tree, and divide-and-conquerDSA Handbook - recursion, backtracking and greedy
What "shape of the recursion" means; Linear: one self-call per frame; Tree: two self-calls per frame; Divide-and-conquer: split, recurse, combine; What it actually costs
Depth · Use it as the shape vocabulary for the tree accounting in Erickson. Memoization detail belongs to the dynamic programming stage.
Focus on
- Tree accounting has three numbers: depth, cost per level, and leaf count. \(T(n) = 2T(n/2) + n\) with \(T(1) = 1\) gives depth 10 and 11264 at \(n = 1024\), checked with a five-line evaluator.
- One-sided recursion is a path, not a tree: \(T(n) = T(n/2) + n\) sums to \(\Theta(n)\), while \(T(n) = T(n-1) + 1\) sums to \(\Theta(n^2)\). Dropping the combine cost changes the answer.
- Groups of five guarantee a pivot that discards a fixed fraction on both sides, giving \(T(n)\) below \(T(n/5) + T(7n/10) + O(n)\), which sums to linear because 1/5 plus 7/10 is below 1.
- Fixed-pivot quickselect on sorted input recurses on \(n - 1\) each level and is quadratic. The randomness or the median of medians is doing the work, not the partition loop.
Reproduce closed-book
sorted(xs)[k] with pytest on 300 seeded lists of length 1 to 60 with duplicates. Finally count comparisons for first-element-pivot quickselect (\(n - 1\) per partition) on sorted range(1000) with \(k = 999\): 499500, which is \(n(n - 1)/2\).Traps
- Reading \(T(n) = T(n/2) + n\) as \(n \log n\). Halving with linear combine is a geometric series summing below \(2n\); the log appears only when both halves are solved.
- Applying tree intuition to unbalanced splits without checking: \(T(n) = T(3n/4) + T(n/4) + n\) is still \(n \log n\), but \(T(n) = T(n-1) + n\) is quadratic.
- Quoting linear quickselect without naming the pivot policy. First-element pivot on sorted input is the quadratic case, and this unit proves the recurrence rather than the partition code.
Practice
Attempt cold with merge-sort counting. Examples: [1, 3, 2, 3, 1] returns 2; [2, 4, 3, 5, 1] returns 3. Write the recurrence your code satisfies, then differentially test against the \(O(n^2)\) double loop on 200 seeded arrays up to length 40, including negatives and values near \(2^{31}\).
After submitting, read the AlgoMaster Reverse Pairs lesson (https://algomaster.io/learn/dsa/reverse-pairs) and compare where the count is taken relative to the merge.
LeetCode 215: Kth Largest Element in an Array
Resubmit with your deterministic median-of-medians select, with no random pivot. Examples: [3, 2, 1, 5, 6, 4] with \(k = 2\) returns 5; [3, 2, 3, 1, 2, 4, 5, 5, 6] with \(k = 4\) returns 4.
The partition unit solved this problem with random pivots; this pass checks the median-of-medians code on the judge's sorted and duplicate-heavy tests.
Self-test
-
Solve \(T(n) = T(n/2) + n\) with \(T(1) = 1\).
\(\Theta(n)\). Level costs are \(n\), \(n/2\), \(n/4\) and so on, summing below \(2n\). The recursion is a single path, so there is no leaf multiplicity. -
Give the quickselect worst case: input, pivot rule, and comparison count.
Sorted input with a first-element pivot and the largest element as the target. Every partition splits into 0 and \(n - 1\), so comparisons total \(n(n - 1)/2\): 499500 for \(n = 1000\). A middle target is still quadratic, about \(3n^2/8\). -
Why is median-of-medians linear?
Its recurrence is \(T(n)\) below \(T(n/5) + T(7n/10) + O(n)\). The subproblem fractions sum to 9/10, below 1, so the level costs form a convergent geometric series. -
What does this unit own that the partition unit does not, and vice versa?
This unit owns recurrence analysis and deterministic median of medians. The partition unit owns the partition invariant, the quickselect implementation, adversarial pivots, and the top-k tradeoff.
Completion criterion
Stop when
You derive the three recurrences without notes, Reverse Pairs is accepted, and your median-of-medians select matches sorted on every small test and is accepted on LC 215.
Leads to
- 2.2 Partitioning, quicksort, quickselect and top-k Partition invariant, quickselect implementation, adversarial pivots, and heap versus quickselect versus full sort.
- 4.5 Randomized correctness, expected cost and selection Expected-cost analysis of random pivots.
Comes after
- 2.2 Partitioning, quicksort, quickselect and top-kRecurrence analysis and deterministic median-of-medians live there; this unit uses only the random-pivot form.
- 4.1 Recursion contracts, backtracking and sound pruningRead the recursion-tree cost of your enumeration before calling it slow.
Resources for this unit
- DSA Handbook - recursion, backtracking and greedy Study Part 7, Part 10 and the relevant foundations on recursion and probability. Write the state definition or greedy claim before opening code.
- Algorithms - recursion, backtracking and greedy Use the recursion, backtracking, divide-and-conquer and greedy chapters for recurrence derivations, proof templates and counterexamples.
Also in this section
- AlgoMaster DSA - decomposition and greedy slice Attempt N-Queens and Gas Station cold, then implement reservoir sampling and test its output distribution over fixed-seed trials. Add another judged problem only for a diagnosed weakness.
- MIT 6.042J - probability and randomized algorithms Use the probability, expectation and concentration readings to derive sampling probabilities and distinguish expected from high-probability guarantees.
- Algorithms lecture notes - randomized algorithms Use note 1 Discrete Probability, note 2 Nuts and Bolts (randomized quicksort, with QuickSelect in its exercises), note 4 Tail Inequalities and note 5 Hashing to derive expected costs, separate expected from high-probability guarantees, and analyze hashing behavior.