Divide and
Conquer

Three steps

Every divide-and-conquer algorithm follows the same recursive blueprint:

When to use D&C

• Problem has optimal substructure — solution builds from sub-solutions
• Subproblems are independent — no shared mutable state
• Combining is efficient — merging cost must not dominate
• Examples: sorting, searching, geometric problems, algebraic transforms

Defining runtime recursively

A D&C algorithm with a subproblems of size n/b and O(nd) combine work has recurrence:

T(n) = a · T(n/b) + O(n^d)

Solution methods

• Substitution — guess the form, prove by induction
• Recursion tree — draw the tree, sum work per level
• Master theorem — closed-form for T(n) = aT(n/b) + O(nd)

Common recurrence examples

The canonical D&C sort

Properties

• Time: O(n log n) worst, average, and best case
• Space: O(n) auxiliary (merge buffer)
• Stable: yes — equal elements preserve original order
• Not in-place: requires extra memory proportional to input

Pseudocode

merge_sort(A, lo, hi):
    if hi - lo <= 1: return
    mid = (lo + hi) / 2
    merge_sort(A, lo, mid)
    merge_sort(A, mid, hi)
    merge(A, lo, mid, hi)

merge(A, lo, mid, hi):
    L = A[lo..mid]
    R = A[mid..hi]
    i = j = 0, k = lo
    while i < |L| and j < |R|:
        if L[i] <= R[j]:
            A[k++] = L[i++]
        else:
            A[k++] = R[j++]
    copy remaining L or R into A

Recursion tree

Level 0:     n work  (1 merge of n)
Level 1:     n work  (2 merges of n/2)
Level 2:     n work  (4 merges of n/4)
  ...
Level log n: n work  (n merges of 1)

Total: n · log n

Inversion counting

Merge sort can count inversions during the merge step. When a right-side element is chosen before left-side elements, it crosses over all remaining left elements — add that count.

Practical variants

Algorithm

Complexity

Pseudocode (Lomuto)

quicksort(A, lo, hi):
    if lo < hi:
        p = partition(A, lo, hi)
        quicksort(A, lo, p - 1)
        quicksort(A, p + 1, hi)

Why Quick Sort wins in practice

• In-place: O(log n) stack space vs O(n) for merge sort
• Cache-friendly: sequential access during partitioning
• Small constant: fewer data movements on average
• Randomised pivot eliminates adversarial worst case

Classic binary search

binary_search(A, target):
    lo, hi = 0, len(A) - 1
    while lo <= hi:
        mid = lo + (hi - lo) / 2
        if A[mid] == target: return mid
        elif A[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

Time: O(log n) — recurrence T(n) = T(n/2) + O(1), Master Case 2

Space: O(1) iterative, O(log n) recursive

Off-by-one pitfalls

• Use lo + (hi - lo) / 2 not (lo + hi) / 2 to avoid overflow
• Clarify inclusive vs exclusive bounds before coding
• Test on arrays of size 0, 1, 2 — most bugs hide there

Variants

Strassen's insight (1969)

Divide each n×n matrix into four n/2 × n/2 submatrices. Naive block multiply needs 8 recursive multiplications. Strassen reduces this to 7.

The seven products

M1 = (A11 + A22)(B11 + B22)
M2 = (A21 + A22) B11
M3 = A11 (B12 - B22)
M4 = A22 (B21 - B11)
M5 = (A11 + A12) B22
M6 = (A21 - A11)(B11 + B12)
M7 = (A12 - A22)(B21 + B22)

Result blocks computed from M1..M7 using only addition/subtraction.

Complexity comparison

Problem

Given n points in the plane, find the pair with minimum Euclidean distance. Brute force: O(n2).

D&C approach — O(n log n)

1. Sort points by x-coordinate
2. Divide — split into left and right halves by median x
3. Conquer — recursively find closest pair in each half: dL, dR
4. Combine — let d = min(dL, dR). Check pairs straddling the dividing line within a strip of width 2d

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

The strip trick

Problem

Multiply two n-digit integers. School algorithm: O(n2).

Karatsuba's trick (1960)

Split each number into high and low halves:

x = x_H · B^m + x_L
y = y_H · B^m + y_L

Naive: 4 multiplications of n/2-digit numbers. Karatsuba uses 3:

z0 = x_L · y_L
z2 = x_H · y_H
z1 = (x_L + x_H)(y_L + y_H) - z0 - z2

x·y = z2·B^2m + z1·B^m + z0

Complexity

Recurrence: T(n) = 3T(n/2) + O(n)

Master Case 1: log2(3) ≈ 1.585 > 1 → O(n1.585)

Multiplication algorithm hierarchy

D&C approach — O(n log n)

1. Divide — split array at midpoint
2. Conquer — recursively find max subarray in left and right halves
3. Combine — find max subarray crossing the midpoint (linear scan)
4. Return maximum of left, right, and crossing

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

Kadane's algorithm — O(n)

kadane(A):
    max_here = max_so_far = A[0]
    for i = 1 to n-1:
        max_here = max(A[i],
                       max_here + A[i])
        max_so_far = max(max_so_far,
                         max_here)
    return max_so_far

Single pass, O(1) space. Essentially dynamic programming.

The selection problem

Find the k-th smallest element in an unsorted array.

Quickselect — expected O(n)

Partition around a random pivot. Recurse only into the side containing index k. Expected O(n), worst case O(n2).

Median of medians — worst-case O(n)

1. Divide array into groups of 5
2. Find the median of each group (brute force)
3. Recursively find the median of those medians → pivot
4. Partition around this pivot
5. Recurse into the correct side

Why groups of 5?

The pivot is guaranteed to be between the 30th and 70th percentile. Each recursive call eliminates at least 30% of elements:

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

This solves to O(n) because 1/5 + 7/10 = 9/10 < 1.

In practice

The Discrete Fourier Transform (DFT)

Given a sequence of n complex numbers, the DFT computes n frequency components. Naive evaluation: O(n2).

Cooley–Tukey FFT (1965)

Divide the DFT into two half-size DFTs on even-indexed and odd-indexed elements:

X[k]     = E[k] + ω^k · O[k]
X[k+n/2] = E[k] - ω^k · O[k]

where ω = e^{-2πi/n}
E = DFT of even elements
O = DFT of odd elements

Complexity

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

Master theorem Case 2. Reduces DFT from O(n2) to O(n log n).

The butterfly operation

One addition and one subtraction, multiplied by a twiddle factor. Maps naturally to hardware and SIMD.

Applications

• Polynomial multiplication — multiply two degree-n polynomials in O(n log n) instead of O(n2)
• Big integer multiplication — Schonhage–Strassen uses FFT for O(n log n log log n)
• Signal processing — spectral analysis, filtering, convolution
• Audio/image compression — MP3, JPEG rely on DCT (closely related)
• String matching — convolution-based pattern matching

Related transforms

Natural parallelism

D&C subproblems are independent — they can run on separate cores, threads, or machines without synchronisation until the combine step.

Fork-join model

fork-join quicksort(A, lo, hi):
    if hi-lo < THRESHOLD:
        insertion_sort(A, lo, hi)
        return
    p = partition(A, lo, hi)
    fork: quicksort(A, lo, p-1)
    fork: quicksort(A, p+1, hi)
    join

Work and span

Practical frameworks

Pitfalls

• Stack overflow — deep recursion on large inputs. Use iterative bottom-up or increase stack size
• Small subproblem overhead — recursive calls on tiny arrays waste function-call overhead. Switch to insertion sort below 16–32 elements
• Worst-case pivot — deterministic Quick Sort on sorted input is O(n2). Always randomise or use median-of-three
• Unnecessary copying — naive merge sort copies arrays at every level. Use index-based merging with a shared buffer
• Integer overflow — (lo + hi) / 2 overflows for large arrays. Use lo + (hi - lo) / 2

Optimisations

Standard library sort implementations

D&C beyond sorting

Key takeaways

• Divide and conquer is a fundamental paradigm: divide, conquer, combine
• The Master Theorem provides closed-form O-notation for most D&C recurrences
• Merge Sort is the stable O(n log n) baseline; Quick Sort wins in practice
• Strassen, Karatsuba, and FFT beat "obvious" lower bounds via clever decomposition
• Binary search is the simplest D&C — master its variants and off-by-one traps
• D&C is naturally parallel: independent subproblems map to cores/machines
• Real-world implementations are hybrid: switch strategies at small sizes and degenerate inputs

Recommended reading