Chapter 3 · Divide and Conquer

01 The Divide & Conquer Paradigm

"Divide and conquer refers to a class of algorithmic techniques in which one breaks the input into several parts, solves the problem on each part recursively, and then combines the solutions to these subproblems into an overall solution."

✂️

1 · Divide

Split the input into smaller subproblems, usually of roughly equal size.

🔁

2 · Conquer

Solve each subproblem recursively. The base case is small enough to solve directly.

🔗

3 · Combine

Merge the sub-solutions into a solution for the original problem.

Analysis method

The running time of a D&C algorithm is naturally expressed as a recurrence relation: T(n) = aT(n/b) + f(n), where a subproblems of size n/b are solved, and combining takes f(n) time. The Master Theorem often gives a closed-form solution.

02 Counting Inversions

This problem arises directly from collaborative filtering — matching users by taste. The key insight: two rankings are "similar" when few pairs are out of order. How many pairs need to be swapped?

Definition

Inversion

Given an array A[1:n], two indices i < j form an inversion if A[i] > A[j]. The number of inversions measures how far the array is from being sorted. A perfectly sorted array has 0 inversions; the worst case has C(n,2) = n(n−1)/2 inversions.

Why Not Naïve O(n²)?

Checking every pair takes O(n²). Connection to insertion sort: each swap in insertion sort eliminates exactly one inversion, so its runtime is O(n + I) where I = inversions. But in the worst case, I = Θ(n²).

The Trick: Modified Merge Sort

During the merge step, when we pick an element from the right subarray over an element from the left, all remaining left elements form inversions with it. We count these "cross-inversions" for free during the merge.

Algorithm — O(n log n)

NumberOfInversions

NumberOfInversions(A[p:r]): inv = 0 if p < r: q = ⌊(p+r)/2⌋ inv += NumberOfInversions(A[p:q]) // left inversions inv += NumberOfInversions(A[q+1:r]) // right inversions inv += NumberOfInversionsWithMerge(A[p:q], A[q+1:r]) // cross-inversions return inv // During merge: if A[i'] > A[j'], count (q − i' + 1) new inversions // because all remaining left elements are > A[j']

The key correctness argument: when A[i'] > A[j'] during merge, all elements A[i'], A[i'+1], …, A[q] in the left half are also > A[j'] (since the left is sorted). So we count exactly q − i' + 1 new inversions in one step.

🔢 Inversion Counter Interactive

Array: [4, 3, 1, 2]. Press Next to count inversions via merge sort.

Inversions found: 0

Phase: —

Inversions log will appear here…

\[T(n) = 2T(n/2) + O(n) \implies T(n) = O(n \log n)\]

Same recurrence as merge sort — because it IS a modified merge sort.

03 Maximum Profit (Investment Problem)

Given stock prices A[1:n] over n days, find buy day i and sell day j ≥ i maximizing profit A[j] − A[i].

D&C Strategy — 3 Cases

MaximalIncrease

Split A[1:n] at midpoint m. The optimal (buy, sell) pair must fall into exactly one of three cases:

⬅️

Case 1 — Left only

Both i, j ≤ m. Solve recursively on A[1:m].

➡️

Case 2 — Right only

Both i, j > m. Solve recursively on A[m+1:n].

↔️

Case 3 — Crossing

i ≤ m < j. Buy at the minimum of A[1:m], sell at the maximum of A[m+1:n].

Two Versions

Basic Version — O(n log n)

Each call scans subarrays for min/max: O(n) combine step → T(n) = 2T(n/2) + O(n) → O(n log n).

\[T(n) = 2T(n/2) + O(n)\]

Upgraded Version — O(n)

Return min and max recursively alongside the best pair — so combine is O(1). Unrolling the recurrence gives linear time.

\[T(n) = 2T(n/2) + O(1) = O(n)\]

Upgrade Trick — Returning Extra Info

UpgradedMaximalIncrease(A[l:r]) returns four values: the best (buy, sell) pair, and the indices of the overall min and max in A[l:r]. The crossing case then uses the left's min and the right's max directly — no scan needed. Combining min/max of both halves is O(1).

Explicit derivation (n = 2ᵏ)

Expanding T(n) = c₁ + 2T(n/2): after k = log n unrollings we get T(n) = c₁(2ᵏ−1) + 2ᵏT(1) = c₁(n−1) + c₂n = O(n).

04 The Master Theorem

A systematic tool for solving recurrences of the form T(n) = aT(n/b) + f(n).

Master Theorem

T(n) = aT(n/b) + f(n) — where a ≥ 1, b > 1 constants, f(n) positive

Compare f(n) to the watershed function n^log_ba:

Case 1 — f dominated by watershed

If f(n) = O(n^{log_ba − ε}) for some ε > 0, then T(n) = Θ(n^log_ba)

Case 2 — f matches watershed

If f(n) = Θ(n^log_ba), then T(n) = Θ(n^log_ba log n)

Case 3 — f dominates watershed

If f(n) = Ω(n^{log_ba + ε}) for some ε > 0, AND af(n/b) ≤ cf(n) for some c < 1, then T(n) = Θ(f(n))

Four Worked Examples from the Notes

Recurrence	a, b, f(n)	Watershed n^log_ba	Case	Result
T(n) = 9T(n/3) + n	a=9, b=3, f=n	n^log₃9 = n²	Case 1 (ε=1)	Θ(n²)
T(n) = T(2n/3) + 1	a=1, b=3/2, f=1	n^log₃/₂1 = 1	Case 2	Θ(log n)
T(n) = 3T(n/4) + n log n	a=3, b=4, f=n log n	n^log₄3 ≈ n^0.79	Case 3 (ε≈0.2)	Θ(n log n)
T(n) = 2T(n/2) + n log n	a=2, b=2, f=n log n	n^log₂2 = n	⚠ Master fails!	Θ(n log²n)

Edge case — Master Theorem fails

For T(n)=2T(n/2)+n log n: f(n) = n log n grows faster than n, but only by a log factor — not polynomially. Since f(n)/n^log₂2 = log n = o(n^ε), Case 3 doesn't apply. The Master Theorem has no answer here. A refined analysis gives T(n) = Θ(n log² n).

05 Interactive Master Theorem Calculator

🔑 Master Theorem Calculator Interactive

a (subproblems)

b (size factor)

f(n) exponent

Setting f(n) exponent = k means f(n) = nᵏ (for log n terms use Case 2 directly). Examples preloaded above use Merge Sort defaults (a=4, b=2, f=n¹).

06 Karatsuba's Fast Integer Multiplication

Multiplying two n-bit integers naïvely: O(n²). Can divide-and-conquer help?

The Obvious Split — Still O(n²)

Write x = x₁·2^n/2 + x₀ and y = y₁·2^n/2 + y₀. Then:

\[xy = x_1y_1 \cdot 2^n + (x_1y_0 + x_0y_1) \cdot 2^{n/2} + x_0y_0\]

Four n/2-bit multiplications → T(n) = 4T(n/2) + O(n). By Master Theorem: T(n) = O(n^log₂4) = O(n²). No improvement!

Karatsuba's Trick — Three Recursive Calls

Observe that x₁y₀ + x₀y₁ = (x₁+x₀)(y₁+y₀) − x₁y₁ − x₀y₀. The three products on the right side reuse x₁y₁ and x₀y₀ which we compute anyway!

Karatsuba

P₁ = x₁y₁ ← recursive call 1
P₂ = x₀y₀ ← recursive call 2
P₃ = (x₁+x₀)(y₁+y₀) ← recursive call 3
xy = P₁·2ⁿ + (P₃ − P₁ − P₂)·2^n/2 + P₂

\[T(n) = 3T(n/2) + O(n) \implies T(n) = O(n^{\log_2 3}) = O(n^{1.585})\]

Naive schoolbook

O(n²)

D&C 4-way

O(n²) still!

Karatsuba (3-way)
O(n¹·⁵⁸⁵)

The pattern

Saving one recursive call (4→3) saves a factor of n^0.415 — substantial for large n. This same trick of "reducing recursions by algebra" drives both Karatsuba and Strassen.

07 Strassen's Fast Matrix Multiplication

Standard n×n matrix multiply needs n³ operations. Partition A, B, C into 2×2 blocks of n/2×n/2 submatrices:

\[\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{pmatrix}=\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{pmatrix}\]

Standard Blocking — 8 multiplications

C₁₁ = A₁₁B₁₁ + A₁₂B₂₁
C₁₂ = A₁₁B₁₂ + A₁₂B₂₂
C₂₁ = A₂₁B₁₁ + A₂₂B₂₁
C₂₂ = A₂₁B₁₂ + A₂₂B₂₂

T(n) = 8T(n/2) + O(n²) → O(n³) — still cubic!

Strassen — 7 multiplications

P₁ = A₁₁(B₁₂−B₂₂)
P₂ = (A₁₁+A₁₂)B₂₂
P₃ = (A₂₁+A₂₂)B₁₁
P₄ = A₂₂(B₂₁−B₁₁)
P₅ = (A₁₁+A₂₂)(B₁₁+B₂₂)
P₆ = (A₁₂−A₂₂)(B₂₁+B₂₂)
P₇ = (A₁₁−A₂₁)(B₁₁+B₁₂)

Recombining with 7 Products

C₁₁ = P₅ + P₄ − P₂ + P₆
C₁₂ = P₁ + P₂
C₂₁ = P₃ + P₄
C₂₂ = P₅ + P₁ − P₃ − P₇

\[T(n) = 7T(n/2) + O(n^2) \implies T(n) = O(n^{\log_2 7}) \approx O(n^{2.807})\]

Method	Multiplications	Additions	Total Ops
Standard	8 × (n/2)²	4 × (n/2)²	O(n³)
Strassen	7 × (n/2)²	18 × (n/2)²	O(n²·⁸⁰⁷)

Trade-off

Strassen needs 18 additions vs. standard's 4 — it trades multiplications for additions. Since multiplications are slower (especially for large matrices), this is worthwhile asymptotically. For small n, the constant overhead makes it slower than the standard algorithm.

Non-powers of 2

For general n, pad A and B with zeros to the smallest power of 2 ≥ n, run Strassen, then extract the top-left n×n block. This gives O(m²·⁸¹) = O((2n)²·⁸¹) = O(n²·⁸¹).

08 Fast Polynomial Multiplication (FFT)

Given polynomials A(x) of degree m−1 and B(x) of degree n−1, compute C(x) = A(x)·B(x) of degree m+n−2, where cₖ = Σᵢ₊ⱼ₌ₖ aᵢbⱼ.

Naive convolution: O(mn). FFT does it in O(n log n).

Key Concept

Evaluation-Multiplication-Interpolation

Instead of working with coefficients directly, we convert to "point-value" form — evaluate both polynomials at 2n points, multiply the values pointwise, then convert back to coefficients (interpolation).

📊

1. Evaluate — O(n log n)

Use FFT to evaluate A(x) and B(x) at all 2n-th complex roots of unity ωⱼ = e^2πij/2n.

✖️

2. Multiply — O(n)

Compute C(ωⱼ) = A(ωⱼ)·B(ωⱼ) for each j. Pointwise multiplication is trivially linear.

🔙

3. Interpolate — O(n log n)

Run the inverse FFT to recover the coefficients c₀,…,c₂ₙ₋₁ from the point values.

The FFT Divide & Conquer — Even/Odd Split

Any polynomial A(x) can be split into its even-index and odd-index coefficients:

\[A(x) = A_{\text{even}}(x^2) + x\, A_{\text{odd}}(x^2)\]

where A_even(x) = a₀ + a₂x + a₄x² + … and A_odd(x) = a₁ + a₃x + a₅x² + …

Evaluating at ωⱼ² = e^2πij/n (the n-th roots of unity) means we've reduced evaluating one degree-(n−1) polynomial at 2n points to evaluating two degree-(n/2−1) polynomials at n points.

\[T(n) = 2T(n/2) + O(n) \implies T(n) = O(n \log n)\]

The Inverse FFT (IFFT)

To recover coefficients from point values, we exploit a beautiful algebraic fact: evaluating the polynomial D(x), whose coefficients are the C-values at roots of unity, at the roots of unity again gives us back 2n times each coefficient cₜ. Dividing by 2n recovers C. The IFFT has the same structure as the FFT, so it also runs in O(n log n).

Key property — roots of unity sum to zero

For any (2n)-th root of unity ω ≠ 1: Σₛ₌₀²ⁿ⁻¹ ωˢ = 0. This cancellation is what makes IFFT work — all cross-terms vanish.

Why this matters beyond polynomials

Fast polynomial multiplication is a building block for fast integer multiplication (integers are polynomials with digit coefficients). Combined with Karatsuba, FFT-based multiplication achieves O(n log n log log n) — nearly linear!

09 Closest Pair of Points

Given n points in the plane, find the pair with smallest distance. Naïve: O(n²). D&C achieves O(n log n) — the first sub-quadratic algorithm for this fundamental geometry problem, due to Shamos and Hoey (early 1970s).

Algorithm — O(n log n)

ClosestPair

Pre-sort all points by x-coord (array X) and by y-coord (array Y). Recursive step on set Q, with sorted arrays X, Y: if |Q| ≤ 3: brute-force all pairs Split Q into Q_L (left half) and Q_R (right half) via vertical line ℓ δ_L ← ClosestPair(Q_L) // min distance in left half δ_R ← ClosestPair(Q_R) // min distance in right half δ ← min(δ_L, δ_R) // Cross-strip: find pairs with one point in Q_L, one in Q_R Y' ← points within distance δ of line ℓ, sorted by y-coord for each point p in Y': compare p to next 7 points in Y' // at most 7! update δ if closer pair found return δ

Why Check Only 7 Points?

This is the geometric key. If two points in the strip Y' are within distance δ, they both lie in a rectangle of width 2δ and height δ. This rectangle splits on the dividing line ℓ into two δ×δ halves (one for each side). Within each δ×δ half, no two same-side points are closer than δ (by the recursive guarantee). So each δ×δ box holds at most one point. There are 4 boxes total on each side → 8 boxes, 8 points max, so at most 7 others to check per point.

\[T(n) = 2T(n/2) + O(n) \implies T(n) = O(n \log n)\]

Correctness

The O(n) combine step: splitting X and Y into halves, building Y', and doing the 7-point comparisons all take O(n). The recurrence is T(n) = 2T(n/2) + O(n) — the classic merge sort recurrence — giving O(n log n). Adding the initial sorts (O(n log n)) keeps the total at O(n log n).

Chapter Summary

Problem	Key Insight	Recurrence	Runtime
Counting Inversions	Count cross-inversions during merge	2T(n/2) + O(n)	O(n log n)
Max Profit (basic)	3-case split: left / right / cross	2T(n/2) + O(n)	O(n log n)
Max Profit (upgraded)	Return min/max alongside pair	2T(n/2) + O(1)	O(n)
Karatsuba	3 recursive calls instead of 4	3T(n/2) + O(n)	O(n¹·⁵⁸⁵)
Strassen	7 recursive calls instead of 8	7T(n/2) + O(n²)	O(n²·⁸⁰⁷)
FFT	Even/odd split at roots of unity	2T(n/2) + O(n)	O(n log n)
Closest Pair	Strip argument: only 7 checks	2T(n/2) + O(n)	O(n log n)

The master insight

Many of these recurrences are T(n) = 2T(n/2) + O(n) — the same as merge sort! The magic of D&C is that a linear combine step on top of binary recursion yields O(n log n). Saving even one recursive call (4→3 for Karatsuba, 8→7 for Strassen) yields dramatic asymptotic improvements.