Recap: Divide and Conquer

Three steps, one recurrence, a tree to sum it, and three cases to shortcut it.

Divide and conquer comes down to the seven ideas below, each listed with the card that covers it. One picture holds them together: the recursion tree, whose shape is set by how many calls each call makes and how small they are, and whose level totals are the cost.

What the topic established, and which card it was on
The idea	Where
Divide, conquer by recursive calls, combine; the work sits in the divide for quicksort and in the combine for merge sort	Divide and Conquer: Split, Solve, Combine
T(n) = a·T(n/b) + f(n): count the calls that run, read their size from the arguments, add the work outside them	Write the Recurrence From the Code
Total each level of the calls and add the levels; 2T(n/2) + n costs n on each of log₂ n + 1 levels	Solve a Recurrence With a Recursion Tree
Compare f(n) with n^(log_b a): the leaves win, they tie and gain a log n, or the root wins	The Master Theorem's Three Cases
Four calls on halves with linear work are O(n²), not O(n log n), because a sits in the exponent	Assuming Every Halving Recurrence Is O(n log n)
Pass bounds rather than slices, or the copying adds O(n) to every call	Divide and Conquer in Python, Java and TypeScript
One fewer call changes the exponent: three half-size multiplications give O(n^1.585)	Practice: Costing a Faster Way to Multiply Large Numbers

The recurrences to keep are these, each solved by the master theorem.

Divide-and-conquer recurrences at a glance
Algorithm	Recurrence	n^(log_b a)	Case	Cost
Binary search	T(n) = T(n/2) + O(1)	1	2	O(log n)
Largest by halves	T(n) = 2T(n/2) + O(1)	n	1	O(n)
Merge sort	T(n) = 2T(n/2) + O(n)	n	2	O(n log n)
Karatsuba multiplication	T(n) = 3T(n/2) + O(n)	n^1.585	1	O(n^1.585)
Four half-size multiplications	T(n) = 4T(n/2) + O(n)	n²	1	O(n²)

Together they let you name the three steps of a recursive algorithm and say where its work is done, write its recurrence from the code, solve the recurrence with a recursion tree, and shortcut the tree with the master theorem when the recurrence fits its form.

← → move through sections and cards