Divide & ConquerAlgorithmaka D&C, recursive decomposition, master theorem

Divide and Conquer

Split a problem into independent subproblems of the same shape, solve them recursively, and combine the answers; the Master theorem tells you whether the split pays off.

▶ VisualizePattern: Binary SearchPractice (5)
Progress

Overview

Divide and conquer solves an instance of size n by (1) dividing it into a subproblems of size n/b, (2) conquering each recursively, and (3) combining their results in f(n) time. The running time obeys the recurrence T(n) = a · T(n/b) + f(n), and the whole art lies in making a, b, and f(n) such that the recurrence beats the obvious algorithm.

Canonical instances: Merge Sort (a=2, b=2, f=O(n) → O(n log n)), Binary Search (a=1, b=2, f=O(1) → O(log n)), Quick Sort (expected 2T(n/2) + O(n) after a random pivot), Karatsuba multiplication (a=3, b=2, f=O(n) → O(n^1.585)), Strassen (a=7, b=2 → O(n^2.81)), and the Closest Pair of Points of points (2T(n/2) + O(n) after a sort).

The Master theorem compares f(n) against n^(log_b a), the total work of the leaves. Three cases: if the leaves dominate (f(n) polynomially smaller) the answer is Θ(n^(log_b a)); if they tie, Θ(n^(log_b a) · log n); if the combine step dominates (f(n) polynomially larger and regular), Θ(f(n)).

D&C differs from Dynamic Programming in one word: independent. When subproblems overlap, recomputing them is exponential and Memoization (Top-Down DP) is required; when they are disjoint, plain recursion is optimal and the recursion tree is the whole story.

paradigmrecurrencemaster theoremmerge sortquick sortbinary searchKaratsuba

Intuition

A mental model before the formal terms.

Sorting a deck of 1,000 cards alone is slow; splitting it into two piles, handing each to a friend who does the same recursively, and then zipping two sorted piles together takes log₂ 1000 ≈ 10 rounds of zipping, each touching every card once. That is 10 × 1000 operations instead of 1000 × 1000.

Picture the recursion tree: the root does f(n) work, its a children each do f(n/b), and so on for log_b n levels. Sum the work per level. If each level does the same work (a · f(n/b) = f(n), as in merge sort), the total is f(n) · log n. If the work shrinks per level (binary search: one child, constant work), the root dominates. If it grows per level (Karatsuba: three children but only half-size inputs), the leaves dominate and the exponent log_b a is the answer.

Karatsuba is the surprising one: multiplying two n-digit numbers naively needs n² digit products. Splitting each into halves gives 4 half-size products — no gain (4T(n/2) + O(n) = O(n²)). Karatsuba's trick computes the middle term from the other two with three multiplications instead of four, and log₂ 3 ≈ 1.585 < 2. Reducing a by one changes the exponent.

How it works

  1. Divide: choose a split. Usually by index (mid = (lo + hi) / 2), sometimes by value (quick sort partitions around a pivot), sometimes by structure (left/right subtree, x-coordinate median).
  2. Conquer: recurse on each part. Base case: an instance small enough to solve directly (size 0 or 1, or a small constant where insertion sort beats recursion).
  3. Combine: merge results. This is where the algorithm-specific insight lives — merging sorted halves, checking the strip across the split line in closest-pair, adding shifted partial products in Karatsuba.
  4. Analyze with the recurrence T(n) = a T(n/b) + f(n): identify a, b, f(n); compare f(n) to n^(log_b a); read off the Master theorem case. If the split is unbalanced (quick sort worst case T(n-1) + O(n)), the theorem does not apply and the tree is O(n) deep.

Why it works

Correctness is by strong induction on n: the base case is solved directly; assuming all smaller instances are solved correctly, the combine step produces a correct answer for size n. The combine step must be a true function of subresults — this is exactly why the subproblems must be independent.

Efficiency comes from balance. Splitting into equal halves gives depth log_b n; if every level does O(n) work the total is O(n log n), and log n is tiny (≈ 30 for n = 10^9). An unbalanced split (sizes 1 and n−1) gives depth n and destroys the gain, which is why Quick Sort needs a random or median-of-three pivot.

Master theorem, informally: count leaves. a^(log_b n) = n^(log_b a) leaves each doing constant work. If f(n) grows slower than that, the leaves win; faster, the root wins; equal, every level ties and you pay log n levels.

Recognition

How to tell a problem wants this.

  • The problem on the whole input equals a cheap function of the problem on two halves ("count inversions", "maximum subarray", "closest pair", "skyline").
  • Sorted input or a monotone property lets you discard half the input per step (O(log n) — Binary Search and friends).
  • Constraints of n ≤ 10^5..10^6 with a quadratic brute force — you need n log n, and the halves are independent (if they overlap, think Dynamic Programming).
  • Arithmetic on huge numbers or matrices where the naive algorithm is n² or n³ — Karatsuba/Strassen-style splits reduce the exponent.
“sorted array” → Binary Search“merge k sorted” → Divide and Conquer

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Merge Sort visualization.

29
0
10
1
14
2
37
3
13
4
5
5
42
6
21
7
1/54Start with 8 elements. Merge sort splits the array in halves until pieces of size one, then merges sorted pieces back together.
Left halfRight halfHeads being comparedMerged / sorted
PseudocodeLearn Merge Sort →
1mergeSort(a, lo, hi):
2  if lo >= hi: return
3  mid = (lo + hi) // 2
4  mergeSort(a, lo, mid)
5  mergeSort(a, mid+1, hi)
6  merge(a, lo, mid, hi):
7    i = lo, j = mid+1, buf = []
8    while i <= mid and j <= hi:
9      if a[i] <= a[j]: buf.push(a[i++]) else buf.push(a[j++])
10    append leftovers of both halves to buf
11    copy buf back into a[lo..hi]
Complexity
best O(n log n)
avg O(n log n)
worst O(n log n)
space O(n)
Speed

Pseudocode

1solve(problem):
2  if size(problem) <= BASE: return direct(problem)
3  parts = divide(problem)              # a parts of size n/b
4  results = [solve(p) for p in parts]  # independent recursion
5  return combine(results)              # f(n) work
6 
7# T(n) = a T(n/b) + f(n); compare f(n) with n^(log_b a):
8#   f smaller  -> Θ(n^(log_b a))       leaves dominate  (Karatsuba)
9#   f equal    -> Θ(n^(log_b a) log n) every level ties (merge sort)
10#   f larger   -> Θ(f(n))              root dominates   (rare)

Implementations

1# Divide and conquer: split into independent subproblems of the same shape,
2# solve recursively, combine. The Master theorem for T(n) = a*T(n/b) + O(n^d)
3# says the cost is decided by comparing d against log_b(a):
4#   d > log_b(a)  ->  O(n^d)          (the combine dominates)
5#   d == log_b(a) ->  O(n^d log n)    (every level costs the same)
6#   d < log_b(a)  ->  O(n^(log_b a))  (the leaves dominate)
7 
8 
91 · Merge sort: a=2, b=2, d=1, so d == log_2(2) and the cost is O(n log n)
10def merge_sort(a: list[int], buf: list[int], lo: int, hi: int) -> None:
11    if hi - lo <= 1:
12        return
13    mid = (lo + hi) // 2
14    merge_sort(a, buf, lo, mid)
15    merge_sort(a, buf, mid, hi)
16 
17    i, j, k = lo, mid, lo
18    while i < mid and j < hi:
19        if a[j] < a[i]:
20            buf[k] = a[j]
21            j += 1
22        else:
23            buf[k] = a[i]
24            i += 1
25        k += 1
26    while i < mid:
27        buf[k] = a[i]
28        i += 1
29        k += 1
30    while j < hi:
31        buf[k] = a[j]
32        j += 1
33        k += 1
34    a[lo:hi] = buf[lo:hi]
35 
36 
372 · Counting inversions is merge sort with one extra line in the combine
38def count_inversions(a: list[int], buf: list[int], lo: int, hi: int) -> int:
39    if hi - lo <= 1:
40        return 0
41    mid = (lo + hi) // 2
42    total = count_inversions(a, buf, lo, mid) + count_inversions(a, buf, mid, hi)
43 
44    i, j, k = lo, mid, lo
45    while i < mid and j < hi:
46        if a[j] < a[i]:
47            total += mid - i  # a[i..mid) are all greater than a[j]
48            buf[k] = a[j]
49            j += 1
50        else:
51            buf[k] = a[i]
52            i += 1
53        k += 1
54    while i < mid:
55        buf[k] = a[i]
56        i += 1
57        k += 1
58    while j < hi:
59        buf[k] = a[j]
60        j += 1
61        k += 1
62    a[lo:hi] = buf[lo:hi]
63    return total
64 
65 
663 · Karatsuba: a=3, b=2, d=1, so log_2(3) ~ 1.585 > 1 and the LEAVES
67# dominate — O(n^1.585) instead of the schoolbook O(n^2)
68def karatsuba(x: int, y: int) -> int:
69    if x < 10 or y < 10:
70        return x * y
71    n = len(str(max(x, y)))
72    half = n // 2
73    p = 10**half
74 
75    a, b = divmod(x, p)
76    c, d = divmod(y, p)
774 · Three multiplications instead of four is the whole trick
78    ac = karatsuba(a, c)
79    bd = karatsuba(b, d)
80    abcd = karatsuba(a + b, c + d) - ac - bd
81    return ac * p * p + abcd * p + bd
82 
83 
845 · When the split does NOT pay off: a=1, b=2, d=0 gives O(log n), which
85# is binary search — the same recurrence shape with a trivial combine
86def binary_search_rec(a: list[int], target: int, lo: int, hi: int) -> int:
87    if lo >= hi:
88        return -1
89    mid = (lo + hi) // 2
90    if a[mid] == target:
91        return mid
92    return binary_search_rec(a, target, mid + 1, hi) if a[mid] < target else binary_search_rec(a, target, lo, mid)
Walkthrough
  1. a[lo:hi] = buf[lo:hi] is slice assignment, which copies the merged range back in one C-level operation rather than an element loop.
  2. divmod(x, p) splits the operand into high and low halves in a single call.
  3. Python integers are unbounded, so Karatsuba works on arbitrarily large operands with no type ceremony — the only language here where the algorithm can be demonstrated at the size where it actually matters.
  4. len(str(max(x, y))) counts decimal digits exactly, which math.log10 would not for very large integers.
  5. (lo + hi) // 2 needs no overflow guard, since Python integers do not overflow.
Complexity (this implementation)
time O(n log n) merge sort and inversions; O(n^1.585) Karatsuba; O(log n) binary search · space O(n) for the buffer, O(log n) recursion depth

CPython already uses Karatsuba internally for int multiplication above about 70 digits, so the hand-written version is slower than x * y.

Language notes
  • CPython's built-in int multiplication switches to Karatsuba above roughly 70 digits, which makes this implementation educational rather than useful.
  • Slice assignment a[lo:hi] = buf[lo:hi] is a single C-level copy and much faster than a Python element loop.
  • divmod returns both halves in one call, which is both faster and clearer than separate // and %.
  • Recursion depth is log n, so RecursionError is not a concern even for very large inputs.
Common mistakes in this language
  • Using math.log10 to count digits of a huge integer, which loses precision and can be off by one.
  • Writing the copy-back as an element loop instead of slice assignment.
  • Expecting the hand-written Karatsuba to beat x * y, which already uses it.
Language differences that matter here
  • Karatsuba is only demonstrable at a useful scale in Python, whose integers are unbounded; JS/TS need BigInt (which brings a number-mixing hazard), and C++ long long caps out far below where the algorithm helps.
  • Copying a range back: Python slice assignment is one call, C++ std::copy is one call, and JS/TS need an explicit loop or an allocating slice.
  • CPython already uses Karatsuba internally above ~70 digits, so the hand-written version is strictly educational there — the other three languages have no such built-in.
  • Overflow-safe midpoints matter in C++ and JS/TS (lo + ((hi - lo) >> 1)) and are unnecessary in Python.

Complexity

Best
O(log n)
Average
O(n log n)
Worst
depends on a, b, f(n)
Space
O(log n) stack (balanced)

T(n) = a T(n/b) + f(n). Binary search O(log n); merge sort / closest pair O(n log n); Karatsuba O(n^1.585); Strassen O(n^2.81). Unbalanced splits (quick sort worst case) degrade to O(n²).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Subproblems are independent and a cheap combine step exists: sorting, counting inversions, closest pair, skyline, polynomial/integer multiplication, matrix multiplication.
  • Half of the input can be discarded per step (a = 1): Binary Search, Quickselect (expected), finding a peak element.
  • The recursion tree is balanced, so depth is O(log n) and the stack stays small.
Avoid it when
  • Subproblems overlap (Fibonacci, edit distance, knapsack): naive D&C recomputes them exponentially many times — use Memoization (Top-Down DP) or Tabulation (Bottom-Up DP).
  • The combine step costs as much as the brute force. Splitting an array to find its maximum is 2T(n/2) + O(1) = O(n) — no better than a loop, with recursion overhead. Four half-size multiplications (4T(n/2) + O(n)) are still O(n²); D&C only pays off when a < b^k for the brute-force exponent k.
  • A linear scan already achieves the lower bound (e.g. Kadane's Algorithm finds the max subarray in O(n); the D&C version is O(n log n)).
  • Tiny inputs: recursion overhead dominates. Real merge sorts switch to Insertion Sort below ~16 elements, and Karatsuba only beats schoolbook multiplication for numbers of hundreds of digits.

Alternatives

Dynamic ProgrammingActivity SelectionKadane's AlgorithmRecursion & Backtracking

Common mistakes

  • Applying the Master theorem to unbalanced splits (T(n) = T(n−1) + O(n)) or to f(n) that is only logarithmically larger than n^(log_b a) — neither fits the three cases.
  • Forgetting the crossing case in the combine step (max subarray, closest pair): the answer may straddle the split line.
  • Using (lo + hi) / 2 in fixed-width integers — overflows for large indices; use lo + (hi − lo) / 2.
  • Copying subarrays at every level (a[:mid] in Python) — correct, but adds O(n) allocation per level; index ranges over one buffer are the idiomatic fix.
  • Confusing D&C with DP: if you find yourself solving the same (i, j) twice, stop and memoize.

Interview patterns

  • Count inversions / reverse pairs / count of smaller numbers after self: merge sort with counting during merge.
  • Maximum subarray via D&C (then contrast with Kadane's Algorithm).
  • Median of two sorted arrays: binary-search partition — a = 1, b = 2.
  • Skyline problem: merge two skylines like merging sorted lists.
  • Pow(x, n) and matrix exponentiation (Fast Exponentiation): T(n) = T(n/2) + O(1).
  • Being asked to "state the recurrence and solve it" — say a, b, f(n), and the Master theorem case out loud.
Interview questions on this
Mock interviews

Example problems

Merge k Sorted ListshardSearch in Rotated Sorted ArraymediumKth Largest Element in an ArraymediumMaximum SubarraymediumPow(x, n)medium