Divide-and-Conquer Recurrences — Mathematics Knowledge System

Overview

A divide-and-conquer algorithm solves a problem of size n by splitting it into a smaller subproblems, each of size n/b, solving each recursively, and then combining the subproblem solutions with f(n) extra work. This translates directly into a recurrence relation T(n) = aT(n/b) + f(n), and reading off the correct (a, b, f(n)) triple from an algorithm's description is the essential first step before the Master Theorem (or any other recurrence-solving method) can be applied. Classic algorithms map onto this template directly: merge sort splits into 2 halves and does Θ(n) work merging (a=2, b=2, f(n)=n); binary search splits into 1 half of size n/2 with O(1) overhead (a=1, b=2, f(n)=1); Karatsuba multiplication splits an n-digit multiplication into 3 subproblems of half the size (a=3, b=2); and Strassen's matrix multiplication splits an n×n matrix multiply into 7 subproblems of size n/2 (a=7, b=2). Getting a, b, and f(n) right — and recognizing when a recurrence does NOT fit this template (e.g., unequal-size subproblems) — is the practical skill this concept builds toward using the Master Theorem.

Intuition

Setting up the recurrence is really just translating an algorithm's pseudocode into arithmetic: 'how many recursive calls does it make?' becomes a; 'how much smaller is each call's input?' becomes b; 'how much non-recursive work happens per call, ignoring the recursion itself?' becomes f(n). The trap to avoid is miscounting a or b — for instance, binary search makes only 1 recursive call (a=1), not 2, even though it conceptually 'looks at two halves' to decide which one to recurse into; only one half is actually explored. Once (a, b, f(n)) are identified correctly, the recurrence is mechanical to solve via the Master Theorem by comparing f(n) to n^(log_b a), the cost the branching structure would produce on its own if the combine step were free.

Formal Definition

Definition

Given an algorithm that divides a size-n input into a subproblems of size n/b and spends f(n) time combining results, the recurrence and its Master Theorem solution are:

T(n) = a\,T(n/b) + f(n), \qquad a \ge 1,\ b > 1

Divide-and-conquer recurrence template

n^{c} = n^{\log_b a} \quad \text{(the 'critical exponent' from branching alone)}

Branching cost

f(n) = O(n^{c-\epsilon}) \implies T(n) = \Theta(n^{c}); \quad f(n) = \Theta(n^{c}) \implies T(n) = \Theta(n^{c}\log n)

Master theorem cases 1 and 2

f(n) = \Omega(n^{c+\epsilon}) \text{ (regularity holds)} \implies T(n) = \Theta(f(n))

Master theorem case 3

Worked Examples

3 recursive calls, each on inputs of half the size, plus linear combine work.
$T(n) = 3T(n/2) + \Theta(n)$
Identify a=3, b=2, and compute the critical exponent.
$n^{\log_2 3} \approx n^{1.585}$
f(n) = n grows slower than n^1.585 (since 1 < 1.585), so Case 1 of the Master Theorem applies.
$f(n) = O(n^{1.585 - \epsilon})$

Answer: T(n) = Θ(n^{log₂3}) ≈ Θ(n^1.585) — faster than the naive Θ(n²) schoolbook multiplication.

Practice Problems

Difficulty 3/10

Binary search makes 1 recursive call on a subarray of half the size, with O(1) overhead to compare against the middle element. Write the recurrence and solve it.

Difficulty 4/10

An algorithm splits its input into 4 subproblems of size n/2 each and spends Θ(n) time combining them. Write and solve the recurrence.

Difficulty 6/10

A close-pairs-of-points algorithm splits n points into 2 halves of size n/2, recurses on each half, then does Θ(n log n) work merging the strip near the dividing line. Write and solve the recurrence.

Quiz

Summary

Divide-and-conquer algorithms produce recurrences of the form T(n) = aT(n/b) + f(n), where a = number of recursive calls, b = shrink factor, f(n) = combine-step cost.
Correctly identifying a, b, and f(n) from an algorithm's description is the prerequisite step before applying the Master Theorem.
Merge sort (a=2,b=2,f(n)=n), binary search (a=1,b=2,f(n)=O(1)), Karatsuba multiplication (a=3,b=2,f(n)=n), and Strassen's algorithm (a=7,b=2,f(n)=n²) are canonical examples of this template.
A common mistake is miscounting the number of recursive calls a — e.g. binary search makes only 1 call, not 2, despite conceptually splitting into two halves.
Karatsuba's T(n)=3T(n/2)+Θ(n) solves to Θ(n^{log₂3})≈Θ(n^1.585), beating naive Θ(n²) multiplication; Strassen's T(n)=7T(n/2)+Θ(n²) solves to Θ(n^{log₂7})≈Θ(n^2.807), beating naive Θ(n³) matrix multiplication.

References

WebsiteWikipedia — Master theorem (analysis of algorithms)
WebsiteWikipedia — Karatsuba algorithm
WebsiteWikipedia — Strassen algorithm