Divide & conquer

Split a problem, solve smaller copies, and combine the answers with recurrence maths. · 9 min read

Divide and conquer is recursion with a particular shape: split the input into smaller independent pieces, solve each piece recursively, then combine their answers. The pattern is powerful because the recursion tree often has only log n levels.

The template

def divide_conquer(problem):
    if small(problem):
        return solve_directly(problem)
    left, right = split(problem)
    a = divide_conquer(left)
    b = divide_conquer(right)
    return combine(a, b)

Interactive visualization: The recursion tree for T(n)=2T(n/2)+n — step through it frame by frame on this page.

Merge sort recurrence

Why merge sort is n log n

T(n) = 2T(n/2) + cn — Two half-sized recursive sorts, then a linear merge.
level 0 work = cn — One problem of size n.
level 1 work = 2 × c(n/2) = cn — Two half-sized problems still total n work.
every level costs cn — The subproblem sizes across a level add to n.
number of levels = log₂ n — Halve until size 1.
cn log₂ n + O(n leaves) — Leaves add linear work, dominated by n log n.

Result: T(n) = O(n log n)

The quick Master Theorem intuition

For recurrences of the form T(n)=aT(n/b)+f(n), compare the combine work f(n) to n^{log_b a}:

If f(n) is smaller, the leaves dominate.
If f(n) is the same size, every level contributes equally → multiply by log n.
If f(n) is larger, the root/combine work dominates.

For merge sort, a=2, b=2, so n^{log₂2}=n; combine work is also n, so the answer is O(n log n).