Divide and conquer

intermediateCommon atGoogleMetaAmazonTrading firmsRead firstRecursionComplexity analysisPractise in the Sandbox →

Divide and conquer splits a problem into a smaller copies of size n/b, solves each recursively, and combines the results with n^d extra work. The cost is decided by one comparison: a vs b^d. If they’re equal every level of the recursion tree costs the same, and you get Θ(n^d log n); merge sort’s Θ(n log n) is exactly this case.

The idea in plain words

You have to count the votes of a whole country. Counting alone would take forever. Instead you split the country into regions, give each region to a team, and each team splits its region again, down to single polling stations. Then the totals flow back up: stations add up into towns, towns into regions, regions into the national result.

That’s the whole pattern, in three moves:

• Divide. Cut the input into smaller pieces of the same kind of problem.
• Conquer. Solve each piece recursively. Tiny pieces (the base case) are solved directly.
• Combine. Merge the pieces’ answers into the answer for the whole.

It pays off when combining is cheap compared to the brute force. Merge sort is the classic case: sorting is hard, but merging two sorted halves takes one linear pass.

The cost question is: how much work happens at each depth of the recursion, and which depth dominates? The visualization answers it.

See it

Pick a recurrence (or a preset), then step through the levels of its recursion tree. The left side shows the subproblems at each depth; the right shows the total work at that depth. Watch the bars: do they grow, stay level, or shrink as you go down?

Recursion tree for T(n) = a·T(n/b) + n^d

step through

T(n)2·T(n/2) + n

a/b^d1.00

log_b a1.000

total work…

verdict…

level being addedwhere the work concentrates

Level 0 is the original call on n = 16. It does n = 16 work outside its recursive calls, then splits into 2 subproblems of size n/2.

↺◀▶ Play▶1 / 6

Try these in order: Merge sort (bars stay level), Split-multiply, 4 products (bars grow: leaves win), Karatsuba (still growing, but more slowly), Quickselect (bars shrink: the root wins).

When to reach for it

The problem says…	Why divide and conquer fits
the answer for the whole can be built from answers for two halves	That’s the combine step. Ask “if I knew the answer for each half, what’s missing?”
“sort”, “count pairs (i, j) with i < j such that…”	Pairs split three ways: both left, both right, or crossing. Crossing pairs are often countable during a merge.
“k-th smallest”, “median”, “top k” without sorting everything	Partition, then recurse into one side only (quickselect).
huge numbers, matrices, polynomials	Splitting plus an algebra trick saves a recursive call (Karatsuba, Strassen, FFT).
a tree, a range, or an interval that splits naturally	Segment trees, binary search and tree DP are all divide and conquer in disguise.

Divide and conquer vs dynamic programming

Both break a problem into subproblems. In divide and conquer the subproblems are disjoint (the left half and the right half don’t overlap), so each is solved once. When subproblems overlap and repeat, plain recursion recomputes them exponentially often; that’s when you switch to memoization or dynamic programming.

How it works

1. Base case. If the input is small enough (one element, one digit, empty), solve it directly and return.
2. Divide. Split the input into a pieces of about n/b each. Splitting by index is O(1); partitioning around a pivot is O(n).
3. Conquer. Call yourself on each piece.
4. Combine. Build the full answer from the pieces’ answers. This step usually holds the cleverness and most of the per-level cost.

Example 1: Karatsuba multiplication

Multiply two n-digit numbers. Write x = a·10^m + b and y = c·10^m + d. Then

x·y = ac·10^(2m) + (ad + bc)·10^m + bd

That needs four half-size products (ac, ad, bc, bd), and four products of size n/2 is T(n) = 4T(n/2) + n = Θ(n²): no better than schoolbook multiplication. Karatsuba’s 1962 trick is that (a+b)(c+d) − ac − bd = ad + bc, so three products are enough. T(n) = 3T(n/2) + n = Θ(n^log₂3) ≈ Θ(n^1.585).

Python

karatsuba.py

def karatsuba(x: int, y: int) -> int:
    """Multiply non-negative ints with 3 half-size products instead of 4. O(n^1.585) digit ops."""
    if x < 10 or y < 10:                       # 1. base case: one side is a single digit
        return x * y
    m = max(len(str(x)), len(str(y))) // 2     # split point, in decimal digits
    p = 10**m
    a, b = divmod(x, p)                        # 2. divide: x = a*10^m + b, y = c*10^m + d
    c, d = divmod(y, p)
    ac = karatsuba(a, c)                       # 3. conquer: three recursive products...
    bd = karatsuba(b, d)
    ad_plus_bc = karatsuba(a + b, c + d) - ac - bd  # ...because (a+b)(c+d) - ac - bd = ad + bc
    return ac * p * p + ad_plus_bc * p + bd    # 4. combine: shifts and adds only, O(n)


if __name__ == "__main__":
    assert karatsuba(1234, 5678) == 7_006_652
    assert karatsuba(0, 99) == 0
    big_a, big_b = 3141592653589793238462643383279, 2718281828459045235360287471352
    assert karatsuba(big_a, big_b) == big_a * big_b
    print("ok")

TypeScript

karatsuba.ts

import assert from "node:assert/strict";

/** Multiply non-negative bigints with 3 half-size products instead of 4. O(n^1.585) digit ops. */
export function karatsuba(x: bigint, y: bigint): bigint {
  if (x < 10n || y < 10n) return x * y; // 1. base case: one side is a single digit
  const m = Math.floor(Math.max(x.toString().length, y.toString().length) / 2);
  const p = 10n ** BigInt(m);
  const [a, b] = [x / p, x % p]; // 2. divide: x = a*10^m + b, y = c*10^m + d
  const [c, d] = [y / p, y % p];
  const ac = karatsuba(a, c); // 3. conquer: three recursive products...
  const bd = karatsuba(b, d);
  const adPlusBc = karatsuba(a + b, c + d) - ac - bd; // ...because (a+b)(c+d) - ac - bd = ad + bc
  return ac * p * p + adPlusBc * p + bd; // 4. combine: shifts and adds only, O(n)
}

assert.equal(karatsuba(1234n, 5678n), 7006652n);
assert.equal(karatsuba(0n, 99n), 0n);
const bigA = 3141592653589793238462643383279n, bigB = 2718281828459045235360287471352n;
assert.equal(karatsuba(bigA, bigB), bigA * bigB);
console.log("ok");

C#

karatsuba.cs

using System.Numerics;

// Multiply non-negative integers with 3 half-size products instead of 4. O(n^1.585) digit ops.
static BigInteger Karatsuba(BigInteger x, BigInteger y)
{
    if (x < 10 || y < 10) return x * y;              // 1. base case: one side is a single digit
    int m = Math.Max(x.ToString().Length, y.ToString().Length) / 2;
    BigInteger p = BigInteger.Pow(10, m);
    BigInteger a = BigInteger.DivRem(x, p, out BigInteger b); // 2. divide: x = a*10^m + b
    BigInteger c = BigInteger.DivRem(y, p, out BigInteger d); //            y = c*10^m + d
    BigInteger ac = Karatsuba(a, c);                 // 3. conquer: three recursive products...
    BigInteger bd = Karatsuba(b, d);
    BigInteger adPlusBc = Karatsuba(a + b, c + d) - ac - bd; // ...since (a+b)(c+d) - ac - bd = ad + bc
    return ac * p * p + adPlusBc * p + bd;           // 4. combine: shifts and adds only, O(n)
}

if (Karatsuba(1234, 5678) != 7006652) throw new Exception("expected 7006652");
if (Karatsuba(0, 99) != 0) throw new Exception("expected 0");
var bigA = BigInteger.Parse("3141592653589793238462643383279");
var bigB = BigInteger.Parse("2718281828459045235360287471352");
if (Karatsuba(bigA, bigB) != bigA * bigB) throw new Exception("big product mismatch");
Console.WriteLine("ok");

Example 2: quickselect (divide, then conquer only one side)

To find the k-th smallest value you don’t need both halves sorted. Partition around a pivot (as in quicksort), see which side rank k falls on, and continue only there. Some books call this decrease and conquer, since only one subproblem survives.

Python

quickselect.py

import random


def quickselect(xs: list[int], k: int) -> int:
    """k-th smallest value (0-based). Expected O(n), worst O(n^2). Leaves xs untouched."""
    if not 0 <= k < len(xs):
        raise IndexError("k out of range")
    a = list(xs)
    lo, hi = 0, len(a) - 1
    while lo < hi:
        p = random.randint(lo, hi)            # 1. random pivot: no fixed input is always bad
        a[p], a[hi] = a[hi], a[p]
        store = lo
        for i in range(lo, hi):               # 2. partition: values < pivot go left
            if a[i] < a[hi]:
                a[i], a[store] = a[store], a[i]
                store += 1
        a[store], a[hi] = a[hi], a[store]     # pivot now sits at its final sorted position
        if k == store:                        # 3. keep only the side that holds rank k
            return a[k]
        if k < store:
            hi = store - 1
        else:
            lo = store + 1
    return a[lo]


if __name__ == "__main__":
    data = [7, 2, 9, 4, 4, 1, 8]
    assert [quickselect(data, k) for k in range(len(data))] == sorted(data)
    assert quickselect([5], 0) == 5
    assert data == [7, 2, 9, 4, 4, 1, 8]      # input not modified
    print("ok")

TypeScript

quickselect.ts

import assert from "node:assert/strict";

/** k-th smallest value (0-based). Expected O(n), worst O(n^2). Leaves xs untouched. */
export function quickselect(xs: readonly number[], k: number): number {
  if (k < 0 || k >= xs.length) throw new RangeError("k out of range");
  const a = [...xs];
  let lo = 0, hi = a.length - 1;
  while (lo < hi) {
    const p = lo + Math.floor(Math.random() * (hi - lo + 1)); // 1. random pivot
    [a[p], a[hi]] = [a[hi], a[p]];
    let store = lo;
    for (let i = lo; i < hi; i++) { // 2. partition: values < pivot go left
      if (a[i] < a[hi]) { [a[i], a[store]] = [a[store], a[i]]; store++; }
    }
    [a[store], a[hi]] = [a[hi], a[store]]; // pivot now sits at its final sorted position
    if (k === store) return a[k]; // 3. keep only the side that holds rank k
    if (k < store) hi = store - 1; else lo = store + 1;
  }
  return a[lo];
}

const data = [7, 2, 9, 4, 4, 1, 8];
assert.deepEqual(data.map((_, k) => quickselect(data, k)), [...data].sort((x, y) => x - y));
assert.equal(quickselect([5], 0), 5);
assert.deepEqual(data, [7, 2, 9, 4, 4, 1, 8]); // input not modified
console.log("ok");

C#

quickselect.cs

// k-th smallest value (0-based). Expected O(n), worst O(n^2). Leaves xs untouched.
static int Quickselect(int[] xs, int k)
{
    if (k < 0 || k >= xs.Length) throw new ArgumentOutOfRangeException(nameof(k));
    int[] a = (int[])xs.Clone();
    int lo = 0, hi = a.Length - 1;
    while (lo < hi)
    {
        int p = Random.Shared.Next(lo, hi + 1);      // 1. random pivot
        (a[p], a[hi]) = (a[hi], a[p]);
        int store = lo;
        for (int i = lo; i < hi; i++)                // 2. partition: values < pivot go left
            if (a[i] < a[hi]) { (a[i], a[store]) = (a[store], a[i]); store++; }
        (a[store], a[hi]) = (a[hi], a[store]);       // pivot now at its final sorted position
        if (k == store) return a[k];                 // 3. keep only the side that holds rank k
        if (k < store) hi = store - 1; else lo = store + 1;
    }
    return a[lo];
}

int[] data = [7, 2, 9, 4, 4, 1, 8];
int[] sorted = [.. data.Order()];
for (int k = 0; k < data.Length; k++)
    if (Quickselect(data, k) != sorted[k]) throw new Exception($"rank {k} wrong");
if (Quickselect([5], 0) != 5) throw new Exception("expected 5");
if (data[0] != 7) throw new Exception("input modified");
Console.WriteLine("ok");

Merge sort lives on the sorting page

Merge sort is the textbook divide-and-conquer algorithm; its code and an animation of the merge are on Sorting. Read it with this page’s recursion tree in mind: 2 halves, n/2 each, an O(n) merge.

What it costs

The master theorem, as a picture

For a recurrence T(n) = a·T(n/b) + Θ(n^d) with a ≥ 1, b > 1:

• Level i of the tree has a^i subproblems, each of size n/b^i, each doing (n/b^i)^d work.
• So level i costs n^d · (a/b^d)^i. The levels form a geometric series with ratio r = a/b^d.
• There are log_b n levels.

A geometric series is dominated by its largest term. That gives the three cases:

Compare	Ratio r = a/b^d	What dominates	T(n)	Example
a < b^d	r < 1, bars shrink	the root	Θ(n^d)	quickselect, good pivots: T(n/2) + n = Θ(n)
a = b^d	r = 1, bars level	every level equally	Θ(n^d log n)	merge sort: 2T(n/2) + n = Θ(n log n); binary search: T(n/2) + 1 = Θ(log n)
a > b^d	r > 1, bars grow	the leaves	Θ(n^(log_b a))	Karatsuba: 3T(n/2) + n = Θ(n^1.585); tree traversal: 2T(n/2) + 1 = Θ(n)

Why the leaves case gives n^(log_b a): the tree has a^(log_b n) leaves, and a^(log_b n) = n^(log_b a) (take log of both sides). Each leaf does O(1) work.

When the master theorem doesn't apply

• Uneven splits, e.g. T(n) = T(n/3) + T(2n/3) + n. Draw the tree anyway: every level costs ≤ n and the deepest path is log_1.5 n, so it’s Θ(n log n). (The general tool is the Akra-Bazzi method.)
• Subtract, not divide, e.g. T(n) = T(n−1) + n. The depth is n, not log n, so it’s Θ(n²). This is quicksort’s worst case.
• Combine cost with a log factor, e.g. T(n) = 2T(n/2) + n log n. It falls between the basic cases; the result is Θ(n log² n).

Why saving one call matters

Going from 4 recursive calls to 3 changes the exponent, not a constant, because the saving repeats at every level.

Digit multiplications: 4 products per split vs 3

drag the slider

digits n = 64

4 recursive products
4^log₂n = n²

4,096

Karatsuba, 3 products
3^log₂n ≈ n^1.585

729

Both split each number in half, 6 times. Saving one product per call looks tiny, but it compounds at every level: Karatsuba does 5.6× fewer digit multiplications at n = 64 (the ratio is (4/3)^6).

Θ(n), Θ(n log n), Θ(n²): the three answers you'll derive most

drag n

O(1)O(log n)O(n)O(n log n)O(n²)O(2ⁿ)

n = 16

O(n): 16 opsO(n log n): 64 opsO(n²): 256 ops

Space

The recursion stack is as deep as the tree: O(log n) for balanced splits, O(n) for lopsided ones (quicksort on sorted input with a first-element pivot). Merge sort also needs an O(n) buffer for merging. Quickselect, written as a loop like above, uses O(1) extra beyond its copy.

Variations you’ll meet

• Merge-based counting. While merging two sorted halves, each element taken from the right half “jumps over” all remaining left elements. Counting those jumps counts crossing pairs in O(n) per level, O(n log n) total. Many “count pairs where…” problems reduce to this.
• Partition-based selection. Quickselect is expected O(n). Median-of-medians (Blum, Floyd, Pratt, Rivest, Tarjan, 1973) guarantees O(n) worst case, but with a big constant; in practice a random pivot wins.
• Closest pair of points. Split by x-coordinate, solve each side, then check only a thin strip around the dividing line. T(n) = 2T(n/2) + O(n) = O(n log n).
• Matrix and polynomial tricks. Strassen multiplies matrices with 7 half-size products instead of 8: Θ(n^2.807). The FFT multiplies polynomials in O(n log n).
• Divide and conquer on a structure. Binary search halves a range; a segment tree stores the combine step’s results so queries reuse them; tree recursion splits at each node.

Pitfalls

• No progress toward the base case. A split that can produce a piece of the same size (e.g. mid = (lo + hi) // 2 with the wrong +1) recurses forever. Check the two-element input by hand.
• Expensive splitting by accident. Slicing (xs[:mid] in Python, slice in JS) copies. Copying at every level adds O(n) per level, which is fine for merge sort but turns an O(log n) binary search into O(n). Pass indices instead.
• Forgetting the crossing case. For “count/find something over pairs or ranges”, the answer is left + right + crossing. The crossing part is the hard bit and the whole point.
• Stack depth. Python’s default recursion limit is 1000. Lopsided splits on 10^5 elements will blow it. Recurse on the smaller side and loop on the larger one, or go iterative.
• Bad pivots. A fixed pivot (first or last element) makes quicksort and quickselect O(n²) on sorted input. Randomize.

In the interview

• State the three steps out loud: “I’ll split into halves, solve each recursively, and combine with a linear merge.”
• Write the recurrence before quoting a complexity: “T(n) = 2T(n/2) + O(n), so a = 2, b = 2, d = 1; a = b^d, so Θ(n log n).” That one line shows you can derive it, not just recall it.
• Name the space cost: recursion depth plus any buffers.
• Expect follow-ups: “Can you do it without recursion?” (bottom-up merge sort), “What’s the worst case?” (bad pivots), “What if the data doesn’t fit in memory?” (external merge sort: sort chunks, then k-way merge them with a heap).

Check yourself

Check yourself

pick one

T(n) = 2T(n/2) + O(1): a function that recurses into both halves and does constant work per call (like summing a binary tree). What is T(n)?

AΘ(log n)BΘ(n)CΘ(n log n)DΘ(n²)

Check yourself

pick one

You find a way to multiply n-digit numbers using 5 products of size n/3 plus linear work. Is it faster than Karatsuba's Θ(n^1.585)?

AYes: 5/3 is less than 3/2BNo: 5 recursive calls is more than 3, so it must be slowerCYes: T(n) = Θ(n^log₃5) ≈ Θ(n^1.465), a smaller exponentDNo: anything with more than 3 recursive calls is slower

Check yourself

pick one

Quickselect with a lucky pivot every time recurses into one half and partitions in linear time: T(n) = T(n/2) + n. Why is the total Θ(n) and not Θ(n log n)?

ABecause there are only log n levelsBBecause the level costs n, n/2, n/4, … form a shrinking geometric series that sums to under 2nCBecause partitioning is O(1)

Practice on your own

Classic textbook exercises, not gym questions:

• Merge sort, both top-down and bottom-up (no recursion: merge runs of width 1, 2, 4, …).
• Find the majority element (appears more than n/2 times) by divide and conquer: the majority of the whole is the majority of one half.
• Closest pair of points in the plane in O(n log n).
• Build a balanced binary search tree from a sorted array.
• Raise a 2×2 matrix to the n-th power in O(log n) multiplications, and use it to compute Fibonacci numbers.

Go deeper

• CLRS, Introduction to Algorithms, 4th ed., ch. 4 “Divide-and-Conquer”: the recursion-tree method and the master theorem with proof.
• Kleinberg and Tardos, Algorithm Design, ch. 5: counting inversions, closest pair, integer multiplication.
• Jeff Erickson, Algorithms, ch. 1 “Recursion”: merge sort, quickselect, Karatsuba, and recursion trees in plain language (free PDF).
• cp-algorithms: K-th order statistic in O(N), on quickselect.

Related

RecursionBase cases, the call stack, and thinking recursively.

SortingMerge sort and quicksort, animated.

Complexity analysisCounting operations and reading recurrences.

Segment treesDivide and conquer, stored so queries reuse it.