Difficulty: Intermediate to Advanced | Prerequisites: Potential method, divide and conquer, Master Theorem (see Part 1 study notes), basic geometry intuition, familiarity with products/logarithms.
These problems extend the core divide-and-conquer toolkit into more challenging territory. The 2D closest-pair algorithm is a classic example of how a clever combine step can keep the overall runtime at O(n log n) even when the naive approach would be quadratic. SlowSort is a deliberately terrible sorting algorithm that illustrates when the Master Theorem breaks down. The Pikachu trading problem (maximum subarray product) introduces the idea of carrying auxiliary information through a divide-and-conquer recursion to handle the cross-boundary case efficiently. If you are comfortable with the basic Master Theorem applications from Part 1, you are ready for these.
The closest-pair algorithm achieves O(n log n) by showing that only a constant number of cross-boundary point comparisons are needed per point, using a geometric packing argument. SlowSort has a recurrence with mixed subproblem sizes that the Master Theorem cannot handle, producing a super-polynomial runtime. The trading card problem reduces to maximum subarray product, solvable in O(n log n) by tracking suffix and prefix products across the midpoint.
Closest pair (2D)
The problem of finding the two points in a set with the smallest Euclidean distance between them. A naive approach checks all pairs in O(n^2); the divide-and-conquer approach runs in O(n log n).
Delta (δ) strip
In the closest-pair algorithm, δ is the minimum distance found in the left and right halves. The strip is the vertical band of width 2δ centred on the median line. Only points inside this strip can form a closer pair across the boundary.
Pigeonhole principle
If n items are placed into m boxes and n > m, at least one box contains more than one item. Used here to bound how many points can fit in a δ × δ square when all points are at least δ apart.
SlowSort
A deliberately inefficient recursive sorting algorithm that sorts both halves, places the overall maximum at the end, then recursively sorts the first n − 1 elements. Its recurrence mixes different subproblem sizes, making it immune to the Master Theorem.
Maximum subarray product
Given an array of multiplicative growth factors, find the contiguous subarray whose product is maximised. This is the multiplicative analogue of the classic maximum subarray sum problem.
Suffix product / prefix product
The product of elements from some starting index to the end of a subarray (suffix), or from the beginning of a subarray to some ending index (prefix). Used in the combine step of the trading card problem.
The divide-and-conquer closest-pair algorithm splits the point set in half by a vertical median line ℓ, recursively finds the closest pair in each half, and takes δ = min(δ_left, δ_right). The only remaining question is whether there exists a pair of points, one from each side, that are closer than δ.
Such a pair can only exist within a vertical strip of width 2δ centred on ℓ. The algorithm collects all points in this strip, sorts them by y-coordinate, and checks each point against a bounded number of subsequent points in the sorted order.
The critical insight is that for any point p in the strip, only a constant number of other points can be within distance δ of p. The argument proceeds geometrically.
Consider a 2δ × δ rectangle centred vertically on p (δ wide on each side of the median). Any point within distance δ of p that lies on the other side of ℓ must fall inside this rectangle.
Proving at most 4 points per side.
Partition the δ × δ square on the left side into four congruent (δ/2) × (δ/2) sub-squares. The diameter of each sub-square (the maximum distance between two points inside it) is δ/2 · √2 = δ√2/2 < δ. Since all points in the left subset are at least δ apart from each other (that is the minimum distance within the left half), each sub-square can contain at most one point from the left subset. By the pigeonhole principle, the left square holds at most 4 points. The same argument applies symmetrically to the right square.
So the full 2δ × δ rectangle holds at most 4 + 4 = 8 points (including p itself).
Why checking 8 subsequent points suffices.
Consider the points in the strip sorted by y-coordinate. For a given point p, any point within distance δ of p must lie within the 2δ × δ rectangle described above. That rectangle contains at most 8 points total (from both sides). Since we are looking at points sorted by y-coordinate, and the rectangle has height δ, any point within distance δ of p is among the next 8 points in the sorted order (at most 7 others besides p, but we check 8 to be safe).
This means the combine step does O(n) work: for each of the at most n points in the strip, we do at most 8 comparisons. The overall recurrence is T(n) = 2T(n/2) + O(n log n) if we sort in each call, or T(n) = 2T(n/2) + O(n) if we maintain a pre-sorted auxiliary list. Either way, T(n) = O(n log n) or O(n log^2 n), depending on the implementation.
SlowSort(A[1..n]) works as follows:
Recursively sort the first half: SlowSort(A[1..⌊n/2⌋])
Recursively sort the second half: SlowSort(A[⌊n/2⌋+1..n])
If the last element of the first half is larger than A[n], swap them (this places the overall maximum at position n)
Recursively sort A[1..n−1]
The algorithm makes two recursive calls on size n/2 (steps 1 and 2), then one recursive call on size n − 1 (step 4), plus O(1) work for the comparison and swap. So:
T(n) = 2T(n/2) + T(n − 1) + O(1)
The Master Theorem requires all recursive subproblems to have the same form: T(n) = k · T(n/b) + f(n). Here, we have a mixture of T(n/2) terms and a T(n − 1) term. The subproblems shrink by different factors (half versus minus one), so the recurrence does not match the required template.
The correct answer from the worksheet options is: T(n) = 2T(n/2) + T(n − 1) + O(1); the Master Theorem does not apply.
The runtime grows faster than any polynomial. Intuitively, after sorting both halves and placing the max at the end, you still need to sort n − 1 elements from scratch. That T(n − 1) term dominates and leads to super-polynomial growth. The exact asymptotic behaviour involves the function n^(log n), which grows faster than n^k for any fixed k.
Given an array A[1..n] of positive real growth factors, find indices i ≤ j that maximise the product A[i] · A[i+1] · ... · A[j]. This represents buying a trading card at the start of day i and selling at the end of day j to maximise the aggregate return.
Suppose you must hold the card on day k (buy on some day i ≤ k, sell on some day j > k). The aggregate growth is A[i] · A[i+1] · ... · A[j].
Split this into two independent parts:
The suffix product from day i to day k: A[i] · A[i+1] · ... · A[k]. To maximise this, scan leftward from k, maintaining a running product, and track the maximum suffix product and the index i that achieves it.
The prefix product from day k+1 to day j: A[k+1] · A[k+2] · ... · A[j]. To maximise this, scan rightward from k+1, maintaining a running product, and track the maximum prefix product and the index j that achieves it.
Multiply the best suffix product by the best prefix product to get the optimal crossing growth. Each scan is O(n), so the total is O(n).
Split A into two halves at the midpoint m = n/2.
The optimal subarray either lies entirely in the left half A[1..m], entirely in the right half A[m+1..n], or crosses the midpoint (i ≤ m < j).
Recursively find the best product in A[1..m].
Recursively find the best product in A[m+1..n].
Use the O(n) algorithm from part (a) with k = m to find the best crossing product.
Return the maximum of the three.
Recurrence: T(n) = 2T(n/2) + O(n). By the Master Theorem (k = 2, b = 2, d = 1, Case 2): T(n) = O(n log n).
A = [0.8, 1.1, 0.95, 1.5, 0.8, 1.25]. Split at m = 3.
Left half: [0.8, 1.1, 0.95]. Best subarray product in left half: 1.1 · 0.95 = 1.045, or just 1.1.
Right half: [1.5, 0.8, 1.25]. Best subarray product in right half: 1.5, or 1.5 · 0.8 · 1.25 = 1.5.
Crossing: best suffix ending at m = 3 is 1.1 · 0.95 = 1.045 (buying on day 2). Best prefix starting at m+1 = 4 is 1.5 (just day 4), or 1.5 · 0.8 · 1.25 = 1.5 (days 4 to 6). So crossing product is 1.045 · 1.5 = 1.5675.
The maximum is 1.5675, achieved by i = 2, j = 6 (or i = 2, j = 4 with product 1.1 · 0.95 · 1.5 = 1.5675 as well).
Closest-pair recurrence: T(n) = 2T(n/2) + O(n) → O(n log n) (with pre-sorted auxiliary list)
Maximum points in δ × δ square: 4 (by pigeonhole, partitioning into four (δ/2) × (δ/2) sub-squares)
Maximum points in 2δ × δ rectangle: 8 (4 per side)
SlowSort recurrence: T(n) = 2T(n/2) + T(n − 1) + O(1) (Master Theorem does not apply)
Maximum subarray product (crossing): max over i ≤ k of (A[i] · ... · A[k]) × max over j > k of (A[k+1] · ... · A[j])
Maximum subarray product (full): T(n) = 2T(n/2) + O(n) → O(n log n)
Students often assume the closest pair must lie on opposite sides of the median line. It may well lie entirely within one half, which is why the recursive calls are essential and the cross-boundary check is only one of three cases.
A frequent mistake with the closest-pair strip is thinking you need to compare every point against every other point in the strip. The geometric packing argument shows that only O(1) comparisons per point are needed.
Students sometimes try to apply the Master Theorem to SlowSort's recurrence. The presence of T(n − 1) alongside T(n/2) means the standard form does not fit. Recognising when the Master Theorem is inapplicable is itself a testable skill.
In the trading card problem, students sometimes forget that the crossing case must be handled separately. The optimal subarray may span the midpoint, and neither recursive call will find it.
⚠️ The closest-pair bounding-rectangle argument is a staple exam question. Be ready to reproduce the pigeonhole proof that at most 4 points from one side fit in a δ × δ square.
⚠️ Recognising when the Master Theorem does not apply is as important as knowing how to use it. SlowSort is the classic example.
⚠️ The maximum subarray product (or sum) pattern, where you handle the crossing case by computing best suffix and best prefix at the boundary, appears in many divide-and-conquer problems. Understand the template.
⚠️ The O(n) subroutine for the constrained crossing case is often the key to getting the full algorithm down to O(n log n). If the crossing step were O(n^2), the whole algorithm would be O(n^2).
True or false: In the closest-pair algorithm, you only need to check points within the 2δ-wide strip for the cross-boundary case. (True. Points further from the median line cannot be closer than δ to any point on the other side.)
Fill in the blank: A δ × δ square can contain at most ______ points that are all pairwise at least δ apart. (4)
True or false: The Master Theorem can be applied to T(n) = 2T(n/2) + T(n − 1) + O(1). (False. The subproblems are of different forms.)
Fill in the blank: In the maximum subarray product problem, the crossing case is handled by computing the best ______ product in the left half and the best ______ product in the right half. (suffix, prefix)
True or false: SlowSort runs in polynomial time. (False. It runs in super-polynomial time.)
Q: In the 2D closest-pair algorithm, why does it suffice to check only 8 subsequent points in the y-sorted strip for each point?
A: The 2δ × δ bounding rectangle around any point p holds at most 8 points total (4 from the left side, 4 from the right). Since the points are sorted by y-coordinate and the rectangle has height δ, all points within distance δ of p appear among the next 8 entries in the sorted list.
Q: Prove that a δ × δ square can contain at most 4 points from a set where all pairwise distances are at least δ.
A: Partition the square into four (δ/2) × (δ/2) sub-squares. The diameter of each sub-square is δ√2/2, which is less than δ. So each sub-square can contain at most one point (two points in the same sub-square would be less than δ apart). Four sub-squares, at most one point each, gives at most 4.
Q: Write the recurrence for SlowSort and explain why the Master Theorem does not apply.
A: T(n) = 2T(n/2) + T(n − 1) + O(1). The Master Theorem requires T(n) = k · T(n/b) + f(n), where all recursive terms divide the input by the same factor b. Here, T(n − 1) reduces the input by 1 rather than by a multiplicative factor, so the standard form does not hold.
Q: Design an O(n) algorithm to find the maximum product subarray that crosses a given index k (i.e. i ≤ k < j).
A: Scan leftward from k, maintaining a running product, and record the maximum suffix product and its starting index i. Scan rightward from k+1, maintaining a running product, and record the maximum prefix product and its ending index j. The crossing product is (best suffix) × (best prefix). Each scan is O(n).
Q: What is the overall recurrence and runtime for the divide-and-conquer maximum subarray product algorithm?
A: T(n) = 2T(n/2) + O(n), since the two recursive calls are on halves and the crossing case is O(n). By the Master Theorem (Case 2): T(n) = O(n log n).
The closest-pair algorithm connects to computational geometry more broadly, including convex hull algorithms and Voronoi diagrams, which also use divide-and-conquer with geometric combine steps.
The maximum subarray product problem is the multiplicative cousin of Kadane's maximum subarray sum problem. The divide-and-conquer approach here generalises to any setting where the combine step can be done in linear time by tracking boundary information.
SlowSort connects to the study of lower bounds and intractability. Understanding why certain recurrences resist closed-form solutions prepares you for topics like undecidability and NP-completeness later in the course.
Closest pair, closest-pair algorithm, 2D closest pair, delta strip, δ-strip, median line, bounding rectangle, pigeonhole principle, packing argument, computational geometry, SlowSort, slow sort, super-polynomial, recurrence relation, Master Theorem inapplicable, maximum subarray product, maximum subarray sum, Kadane's algorithm, crossing subarray, suffix product, prefix product, divide and conquer, Pikachu trading, stock trading, buy and sell, EECS 376, Foundations of Computer Science, University of Michigan