Divide and Conquer

Divide and conquer solves problems by:

Divide: Break the problem into smaller subproblems.
Conquer: Solve each subproblem recursively.
Combine: Merge the subproblem solutions into the overall solution.

Analysis: Master Theorem

Most D&C algorithms have recurrences of the form:

T(n) = aT(n/b) + f(n)

where a = number of subproblems, n/b = subproblem size, f(n) = combine cost.

| Case | Condition | Result | |---|---|---| | 1 | f(n) = O(n^(log_b(a) - ε)) | T(n) = Θ(n^log_b(a)) | | 2 | f(n) = Θ(n^log_b(a) · log^k n) | T(n) = Θ(n^log_b(a) · log^(k+1) n) | | 3 | f(n) = Ω(n^(log_b(a) + ε)) + regularity | T(n) = Θ(f(n)) |

Merge Sort

Divide: Split in half. Conquer: Sort each half. Combine: Merge.

T(n) = 2T(n/2) + O(n) → T(n) = O(n log n). Case 2 of master theorem.

(Detailed implementation in sorting files.)

Quicksort

Divide: Partition around pivot. Conquer: Sort each partition. Combine: Nothing (in-place).

Expected: T(n) = 2T(n/2) + O(n) → O(n log n). Worst: T(n) = T(n-1) + O(n) → O(n²).

Closest Pair of Points

Given n points in 2D, find the pair with minimum distance.

Algorithm

Sort points by x-coordinate.
Divide: Split into left and right halves by median x.
Conquer: Find closest pair in each half recursively: δ_L, δ_R.
Let δ = min(δ_L, δ_R).
Combine: Check if any pair straddling the dividing line is closer than δ.
- Only consider points within δ of the dividing line (the "strip").
- Sort strip points by y-coordinate.
- For each point, compare with the next ≤ 7 points in the strip.

FUNCTION CLOSEST_PAIR(points)
    SORT points BY x-coordinate
    RETURN CLOSEST_REC(points)

FUNCTION CLOSEST_REC(pts)
    n ← length(pts)
    IF n ≤ 3 THEN RETURN BRUTE_FORCE_MIN_DIST(pts)

    mid ← n / 2
    mid_x ← pts[mid].x
    d_left ← CLOSEST_REC(pts[0..mid])
    d_right ← CLOSEST_REC(pts[mid..n])
    d ← MIN(d_left, d_right)

    // Strip: points within d of mid_x
    strip ← all p IN pts WHERE |p.x - mid_x| < d
    // Sort strip by y
    // Check each point against next ≤7 points
    // Update d if closer pair found

    RETURN d

Time: T(n) = 2T(n/2) + O(n log n) → O(n log² n). With a clever merge step: O(n log n).

Strassen's Matrix Multiplication

Multiply two n×n matrices faster than the naive O(n³).

Naive

C = A × B
Cᵢⱼ = Σₖ Aᵢₖ × Bₖⱼ

8 recursive multiplications of n/2 × n/2 submatrices: T(n) = 8T(n/2) + O(n²) → O(n³).

Strassen's Insight

Reduce 8 multiplications to 7 using clever linear combinations:

M₁ = (A₁₁ + A₂₂)(B₁₁ + B₂₂)
M₂ = (A₂₁ + A₂₂)B₁₁
M₃ = A₁₁(B₁₂ - B₂₂)
M₄ = A₂₂(B₂₁ - B₁₁)
M₅ = (A₁₁ + A₁₂)B₂₂
M₆ = (A₂₁ - A₁₁)(B₁₁ + B₁₂)
M₇ = (A₁₂ - A₂₂)(B₂₁ + B₂₂)

C₁₁ = M₁ + M₄ - M₅ + M₇
C₁₂ = M₃ + M₅
C₂₁ = M₂ + M₄
C₂₂ = M₁ - M₂ + M₃ + M₆

T(n) = 7T(n/2) + O(n²) → O(n^log₂7) ≈ O(n^2.807).

Practical note: Strassen is faster for n ≥ ~32-64. For smaller matrices, the constant factor makes naive multiplication faster. BLAS libraries use Strassen for large matrices, switching to optimized naive for small subproblems.

Best known: O(n^2.371) (Alman-Williams, 2024). Impractical due to enormous constant factors.

Karatsuba Multiplication

Multiply two n-digit numbers faster than O(n²).

Naive

Multiply each digit of the first number with each digit of the second: O(n²).

Karatsuba

For numbers x = x₁ × B^m + x₀ and y = y₁ × B^m + y₀:

xy = x₁y₁ × B^(2m) + ((x₁+x₀)(y₁+y₀) - x₁y₁ - x₀y₀) × B^m + x₀y₀

Only 3 multiplications instead of 4: x₁y₁, x₀y₀, (x₁+x₀)(y₁+y₀).

T(n) = 3T(n/2) + O(n) → O(n^log₂3) ≈ O(n^1.585).

Used in: Big integer libraries (GMP uses Karatsuba for medium-sized numbers, Toom-Cook and FFT-based for larger).

Median of Medians

Find the k-th smallest element in guaranteed O(n) time.

Divide into groups of 5. Find the median of each group.
Conquer: Recursively find the median of the medians.
Use this median as a pivot. Partition around it.
Recurse on the appropriate side.

T(n) = T(n/5) + T(7n/10) + O(n) → T(n) = O(n).

The pivot is guaranteed to be between the 30th and 70th percentile.

Convex Hull (Divide and Conquer)

Sort points by x-coordinate.
Divide into left and right halves.
Recursively find the convex hull of each half.
Merge: Find the upper and lower tangent lines between the two hulls.

T(n) = 2T(n/2) + O(n) → O(n log n).

Fast Fourier Transform (FFT)

Evaluate a polynomial at n points (roots of unity) or compute the DFT.

Cooley-Tukey

Split polynomial into even and odd terms:

P(x) = P_even(x²) + x · P_odd(x²)

Evaluate at n-th roots of unity ω^k. The even and odd polynomials are evaluated at (n/2)-th roots of unity.

T(n) = 2T(n/2) + O(n) → O(n log n).

Applications

Polynomial multiplication: Evaluate both polynomials at n points (FFT), multiply pointwise, interpolate (inverse FFT). O(n log n) vs O(n²).
Large integer multiplication: Represent numbers as polynomials, multiply with FFT. O(n log n).
Signal processing: DFT/IDFT for spectral analysis.
String matching: Convolution-based matching using FFT.

Design Tips

When to Use D&C

Problem can be broken into independent subproblems of the same type.
Subproblems are significantly smaller (typically half).
Combining solutions is efficient.
Overlapping subproblems? → Use DP instead.

Common Patterns

| Pattern | a | b | f(n) | Result | |---|---|---|---|---| | Binary search | 1 | 2 | O(1) | O(log n) | | Merge sort | 2 | 2 | O(n) | O(n log n) | | Karatsuba | 3 | 2 | O(n) | O(n^1.585) | | Strassen | 7 | 2 | O(n²) | O(n^2.807) | | Closest pair | 2 | 2 | O(n log n) | O(n log² n) | | FFT | 2 | 2 | O(n) | O(n log n) |

Applications in CS

Parallel computing: D&C naturally parallelizes — subproblems are independent. Fork-join frameworks (Cilk, Rayon) exploit this.
Cache-oblivious algorithms: D&C algorithms often have good cache behavior without explicit tuning (recursion naturally fits data into cache).
MapReduce: The map phase divides, the reduce phase combines. Fundamentally D&C.
Computational geometry: Convex hull, closest pair, Voronoi diagram, line segment intersection — all use D&C.
Numerical computing: FFT, fast matrix multiplication, fast polynomial operations.