Divide and Conquer

Split a problem into smaller copies of itself, solve each copy, and combine the answers. The recurrence that describes the split tells you the running time.

Overview

The idea

A divide and conquer algorithm has three steps. Divide: split the input into pieces, usually halves. Conquer: solve each piece with the same algorithm, down to a base case small enough to answer directly. Combine: build the answer for the whole input from the answers for the pieces.

Binary search — look at one half — nothing — O(log n)
Merge sort — two halves — merge two sorted lists, O(n) — O(n log n)
Quicksort — partition around a pivot — nothing, the pieces are already in place — O(n log n) expected
Sorted array to balanced BST — the middle value is the root — attach the two subtrees, O(1) — O(n)
Fast power x^n — square x^(n/2) — one multiplication — O(log n) multiplications
Count inversions — two halves — count cross pairs while merging, O(n) — O(n log n)

The pieces must be independent: solving one must not need the answer of another. When the pieces overlap, as in Fibonacci or most path-counting problems, the same recursion repeats work and dynamic programming is the right tool.

Where the time goes: the recursion tree

Merge sort on eight values splits three times and merges three times. Every level of the tree touches all n values once, and there are log2 n levels, so the total is n log n.

0 — 1 — 8 — 8
1 — 2 — 4 — 8
2 — 4 — 2 — 8
3 — 8 — 1 — base cases

The work per level stays at n because the split is balanced. An unbalanced split, such as one piece of size n - 1, gives n levels and O(n²) total. That is exactly what happens to quicksort with a bad pivot.

The master theorem

Write the running time as a recurrence: T(n) = a T(n/b) + f(n), where a is the number of pieces, each piece has size n/b, and f(n) is the cost of dividing and combining. Compare f(n) with n^(log_b a), the total number of leaves. Three cases cover most common algorithms.

Leaves dominate — f(n) grows slower than n^(log_b a) — T(n) = Θ(n^(log_b a)) — tree traversal: 2T(n/2) + O(1) is O(n)
Balanced — f(n) is Θ(n^(log_b a)) — T(n) = Θ(n^(log_b a) log n) — merge sort: 2T(n/2) + O(n) is O(n log n)
Combine dominates — f(n) grows faster than n^(log_b a), and shrinks by a constant factor per level — T(n) = Θ(f(n)) — one piece of half size plus O(n) work, as in quickselect on average, is O(n)

Binary search is T(n) = T(n/2) + O(1): a = 1, b = 2, so n^(log_b a) = n^0 = 1, the same order as f(n), and the balanced case gives O(log n). Karatsuba multiplication is T(n) = 3T(n/2) + O(n): log2 3 is about 1.585, larger than 1, so the leaves dominate and the cost is O(n^1.585), better than the O(n²) schoolbook method. Strassen's matrix multiplication is 7T(n/2) + O(n²), which gives O(n^2.807).

The theorem does not apply when the pieces have different sizes, when a or b is not constant, or when f(n) is not close to a polynomial. For those, draw the recursion tree and add up the levels.

Building a balanced tree from sorted input

Convert Sorted Array to Binary Search Tree is divide and conquer with an O(1) combine step: the middle value becomes the root, the left half becomes the left subtree and the right half becomes the right subtree. Both halves have the same size within one, so the tree is height balanced.

1 — 1 2 3 4 5 6 7 — 4 — 1 2 3 — 5 6 7
2 — 1 2 3 — 2 — 1 — 3
3 — 5 6 7 — 6 — 5 — 7
4 to 7 — single values — leaf

Every value becomes a root exactly once, so the cost is O(n). For a sorted linked list, find the middle with fast and slow pointers, at O(n) per level, for O(n log n) in total; or count the nodes first and build the tree in the order the list is stored, which keeps O(n).

Combining is where the work is

Maximum Binary Tree splits at the largest value instead of the middle: the largest value is the root, everything to its left is the left subtree, everything to its right is the right subtree. On [3, 2, 1, 6, 0, 5] the root is 6, the left subtree is built from 3 2 1 and the right from 0 5.

The split is not balanced, so the cost depends on the input: O(n log n) when the maximum tends to sit near the middle, O(n²) on sorted input where each split leaves one piece of size n - 1. A monotonic stack builds the same tree in O(n), which is the usual follow-up.

Counting inversions shows a combine step that does real work. An inversion is a pair with i a[j]. Sort each half with merge sort and count the inversions inside each half. Then, while merging, every time a value from the right half is taken before the left half is empty, it is smaller than every value still waiting in the left half, so it forms that many inversions. Merge sort finds them all in the O(n) merge.

1 — right — 2 4 5 7 — 4
2 — left — 4 5 7 — 0
2 — right — 4 5 7 — 3
3 — right — 4 5 7 — 3
4, 5 — left — 7 — 0
6 — right — 7 — 1
7 — left — 0

That is the final merge of [5, 2, 4, 7, 1, 3, 2, 6]: 11 cross inversions, plus 3 found inside the halves, so 14 in total, which a brute-force count confirms.

Divide and conquer or dynamic programming?

Do the subproblems overlap? — no, each piece is solved once — yes, the same subproblem comes back
What is stored? — nothing between pieces — a table or memo of solved subproblems
Typical cost — n log n or n^(log_b a) — number of subproblems times work per subproblem
Examples — merge sort, closest pair, fast power — Fibonacci, edit distance, knapsack

> [!TIP] > Draw the recursion tree for a small input. If the same node appears twice, memoize it and you have dynamic programming. If every node is different, you have divide and conquer and the tree gives the cost.

What you will be able to do

Name the divide, conquer and combine steps of an algorithm and write its recurrence.
Read the running time off the recurrence with the master theorem or the recursion tree.
Build a balanced BST from sorted input and explain why the middle element keeps it balanced.
Adapt the merge step to count something, such as inversions.
Tell divide and conquer apart from dynamic programming and say which one a problem needs.

When to use it

The input splits into independent pieces of the same kind, and the answers can be combined
Building a balanced tree from sorted data: the middle is the root
A combine step over sorted halves can count cross pairs, as in inversions and reverse pairs
Splitting a 2D grid into quadrants or a plane into halves, as in Construct Quad Tree and closest pair of points
A brute force is polynomial but halving the problem gives a better recurrence, as in fast power or Karatsuba

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio