JAVA-205 · Lesson 6 of 12 · 19 min
Divide and conquer
▶ Video coming soon A video version of this lesson is on the way.
Merge sort split an array in half, sorted the halves and combined the results. On Tuesday, October 19, 2027, Ingrid gives that pattern its name, divide and conquer, and shows that it is far more general than sorting. Her example comes from Odile, who keeps the shop's daily net sales for the year, takings minus refunds and the cost of parts bought in, and wants to know which run of consecutive days was the best stretch of the year, so she can plan next year's spring clinic around it. Trying every possible run is quadratic. Divide and conquer does it in O(n log n).
The pattern
A divide-and-conquer algorithm has three steps. Divide the problem into smaller problems of the same kind, usually two halves. Conquer each smaller problem by solving it recursively, with a base case for problems small enough to solve directly. Combine the answers to the smaller problems into the answer to the whole. Merge sort divides by splitting at the middle, conquers by sorting the halves and combines by merging. Binary search divides into halves but only needs to conquer one of them, and its combine step is empty.
public class Main {
static int calls = 0;
static int search(int[] sorted, int target, int lo, int hi) {
calls++;
if (lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if (sorted[mid] == target) return mid;
if (sorted[mid] < target) return search(sorted, target, mid + 1, hi);
return search(sorted, target, lo, mid - 1);
}
public static void main(String[] args) {
int[] cents = new int[1000];
for (int i = 0; i < cents.length; i++) cents[i] = 100 + i * 25;
int at = search(cents, 15_000, 0, cents.length - 1);
System.out.println("found at " + at + " after " + calls + " calls");
calls = 0;
System.out.println("missing: " + search(cents, 15_010, 0, cents.length - 1) + " after " + calls + " calls");
}
}found at 596 after 8 calls missing: -1 after 11 calls
What this code does
This is binary search written as divide and conquer: compare with the middle, then solve only the half that can contain the target. Each call halves the range, so a list of 1,000 prices needs about 10 calls. The base case is an empty range, which means the price is missing.
Writing down the cost: recurrences
The cost of a divide-and-conquer algorithm is described by a recurrence, an equation that gives the cost for size n in terms of the cost for smaller sizes. Merge sort makes two calls on halves and then merges n elements: T(n) = 2T(n/2) + n. Binary search makes one call on a half and does a constant amount of other work: T(n) = T(n/2) + 1. Solving a recurrence means finding the Big-O it adds up to.
The easiest way to solve one is to draw the recursion tree: one node for each call, labelled with the work done outside the recursive calls. For merge sort the top node does n work, its two children do n/2 each, its four grandchildren n/4 each, and so on. Every level adds up to n, and there are log₂ n levels, so the total is n log n. For binary search there is one node per level, each doing constant work, over log₂ n levels: log n in total.
A general rule, often called the master theorem, covers the common shape T(n) = aT(n/b) + work done at the top. Intuitively it compares the work at the top of the tree with the number of leaves at the bottom. If the top dominates, the total is the top work. If they balance, every level costs the same and a log n factor appears. If the leaves dominate, the total is the number of leaves. You do not need the formula to use it; the table below lists the cases you will meet.
| Recurrence | Example | Solution |
|---|---|---|
| T(n) = T(n/2) + 1 | Binary search | O(log n) |
| T(n) = T(n/2) + n | Quickselect on average; halving with a linear scan | O(n) |
| T(n) = 2T(n/2) + 1 | Maximum of an array by halves | O(n) |
| T(n) = 2T(n/2) + n | Merge sort; best run of sales | O(n log n) |
| T(n) = T(n − 1) + n | Quicksort with a bad pivot every time | O(n²) |
| T(n) = 2T(n − 1) + 1 | Trying both choices for every item | O(2ⁿ) |
Fast powers
A neat small example is raising a number to a power. Lesson 5's recursive power multiplied exp times. But x¹⁰⁰ = (x⁵⁰)², and x⁵⁰ = (x²⁵)², so you can halve the exponent each time and square the result, with one extra multiplication when the exponent is odd. The recurrence is T(n) = T(n/2) + 1, so the number of multiplications is O(log n) instead of O(n). This fast exponentiation is how cryptography computes powers with exponents hundreds of digits long.
public class Main {
static int mults = 0;
static long slowPower(long x, int n) {
long r = 1;
for (int i = 0; i < n; i++) { r *= x; mults++; }
return r;
}
static long fastPower(long x, int n) {
if (n == 0) return 1;
long half = fastPower(x, n / 2);
mults++;
long r = half * half;
if (n % 2 == 1) { r *= x; mults++; }
return r;
}
public static void main(String[] args) {
System.out.println(slowPower(3, 39) + " after " + mults + " multiplications");
mults = 0;
System.out.println(fastPower(3, 39) + " after " + mults + " multiplications");
mults = 0;
System.out.println("1.0005^365 interest-style growth: " + Math.pow(1.0005, 365));
}
}4052555153018976267 after 39 multiplications 4052555153018976267 after 10 multiplications 1.0005^365 interest-style growth: 1.2001594106776867
What this code does
Both methods compute 3 to the power 39, which still fits in a long. The slow one multiplies 39 times, and the fast one squares half the power and multiplies once more for odd exponents, for 10 multiplications in all. The library's Math.pow works on doubles, and its result is printed as the double gives it.
The best run of sales
Back to Odile's question. Her daily figures are positive on good days and negative on days when refunds and parts purchases outweighed sales. The best stretch is the run of consecutive days with the largest total: the maximum subarray problem. The brute-force method tries every start day and every end day, which is n(n + 1)/2 runs, and keeping a running total for each start makes each run cost one addition: O(n²).
public class Main {
public static void main(String[] args) {
int[] net = {120, -340, 410, 260, -150, 380, -90, -520, 220, 140, -60, 300};
int best = Integer.MIN_VALUE, from = 0, to = 0;
long additions = 0;
for (int i = 0; i < net.length; i++) {
int sum = 0;
for (int j = i; j < net.length; j++) {
sum += net[j];
additions++;
if (sum > best) { best = sum; from = i; to = j; }
}
}
System.out.println("best run: days " + from + " to " + to + ", total " + best);
System.out.println("additions: " + additions);
}
}best run: days 2 to 5, total 900 additions: 78
What this code does
For every start day i the inner loop extends the run one day at a time and keeps the best total seen. Twelve days give 78 possible runs and 78 additions. The best stretch is days 2 to 5, with a total of 900.
Divide and conquer splits the days in half. The best run is either entirely in the left half, entirely in the right half, or it crosses the middle. The first two are found recursively. The crossing run must include the last day of the left half and the first day of the right half, so it is the best sum extending left from the middle plus the best sum extending right, found with two linear scans. The recurrence is T(n) = 2T(n/2) + n, the same as merge sort: O(n log n).
public class Main {
static long steps = 0;
static int best(int[] a, int lo, int hi) {
if (lo == hi) return a[lo];
int mid = lo + (hi - lo) / 2;
int left = best(a, lo, mid), right = best(a, mid + 1, hi);
int sum = 0, leftCross = Integer.MIN_VALUE;
for (int i = mid; i >= lo; i--) { sum += a[i]; steps++; leftCross = Math.max(leftCross, sum); }
sum = 0;
int rightCross = Integer.MIN_VALUE;
for (int j = mid + 1; j <= hi; j++) { sum += a[j]; steps++; rightCross = Math.max(rightCross, sum); }
return Math.max(Math.max(left, right), leftCross + rightCross);
}
public static void main(String[] args) {
int[] net = {120, -340, 410, 260, -150, 380, -90, -520, 220, 140, -60, 300};
System.out.println("best total: " + best(net, 0, net.length - 1));
java.util.Random rnd = new java.util.Random(365);
int[] year = new int[365];
for (int i = 0; i < year.length; i++) year[i] = rnd.nextInt(1201) - 500;
steps = 0;
int b = best(year, 0, year.length - 1);
System.out.println("365 days: best total " + b + " after " + steps + " scan steps (brute force: " + 365 * 366 / 2 + ")");
}
}best total: 900 365 days: best total 43839 after 3138 scan steps (brute force: 66795)
What this code does
best returns the largest of three answers: the best run in the left half, the best in the right half and the best run crossing the middle. The crossing run is built from two scans outwards from the middle. For a made-up year of 365 days from a seeded Random, the scans take 3,138 steps against 66,795 for brute force.
There is an even faster answer, Kadane's algorithm, which is O(n): scan once, keeping the best run that ends today, and reset it to zero whenever it goes negative. It is a small example of dynamic programming, the subject of lesson 11. Divide and conquer is still worth learning here, because the same split-solve-combine reasoning works on problems that have no clever linear trick.
Choosing where to divide
Divide and conquer is fastest when the pieces are balanced, as halves are. Quicksort showed what happens when they are not: a pivot that splits n into 1 and n − 1 turns the recursion tree into a long chain, and O(n log n) becomes O(n²). Good divide-and-conquer algorithms either split exactly in the middle, as merge sort and binary search do, or use randomness to make bad splits unlikely, as quicksort with a random pivot does.
- Make sure the combine step is cheap compared with solving the problem from scratch, ideally linear or less.
- Stop dividing at a small size and solve directly; library sorts switch to insertion sort for pieces of a few dozen elements.
- Check that the pieces are independent. If the same smaller problem appears in many branches, as in Fibonacci, use dynamic programming instead.
- Watch the recursion depth: balanced halving keeps it at about log₂ n, about 20 for a million elements.
Try it yourself
Maximum by halves
Write the recursive method max(int[] a, int lo, int hi) that returns the largest value between indexes lo and hi, inclusive, by finding the maximum of each half and returning the larger.
For the counts in the starter it should print max: 22.
public class Main {
static int max(int[] a, int lo, int hi) {
return a[lo];
}
public static void main(String[] args) {
int[] counts = {14, 9, 22, 6, 9, 3, 17};
System.out.println("max: " + max(counts, 0, counts.length - 1));
}
}Try it yourself
Fast power
Write fastPower(long x, int n) using divide and conquer: compute half = fastPower(x, n / 2), square it, and multiply by x once more when n is odd. The base case is n == 0.
The program should print 1, 1024, 59049 and 4052555153018976267, one per line.
public class Main {
static long fastPower(long x, int n) {
long r = 1;
for (int i = 0; i < n; i++) r *= x;
return r - 1;
}
public static void main(String[] args) {
System.out.println(fastPower(5, 0));
System.out.println(fastPower(2, 10));
System.out.println(fastPower(3, 10));
System.out.println(fastPower(3, 39));
}
}Common mistakes
MistakeSplitting a problem into very unequal pieces.
InsteadSplit in the middle, or use a random choice, so the recursion stays about log n deep.
MistakeMaking the combine step as expensive as the original problem.
InsteadAim for a combine step that is linear or cheaper.
MistakeUsing divide and conquer when the pieces overlap.
InsteadUse dynamic programming to solve each shared subproblem once.
MistakeForgetting the crossing case in problems like the best run of sales.
InsteadConsider answers that span both halves, not only those inside one half.
MistakeRecursing all the way to size 1 when a simple method is faster for small pieces.
InsteadSwitch to a direct method below a small cut-off size.
Summary and key terms
- Divide and conquer divides a problem into smaller problems of the same kind, conquers them recursively and combines their answers.
- Its cost is written as a recurrence such as T(n) = 2T(n/2) + n for merge sort, and drawing the recursion tree shows the total: n work on each of log n levels gives O(n log n), and one call per level with constant work gives O(log n).
- The master theorem compares the work at the top of the tree with the number of leaves.
- Fast exponentiation halves the exponent each step for O(log n) multiplications.
- The maximum subarray problem, finding Odile's best run of sales, takes O(n²) by brute force and O(n log n) by divide and conquer, by combining the best left run, the best right run and the best run crossing the middle.
- Balanced splits, cheap combine steps and independent pieces make divide and conquer work well.
- Divide and conquer
- Solving a problem by splitting it into smaller problems of the same kind, solving them and combining the results.
- Recurrence
- An equation giving an algorithm's cost for size n in terms of its cost for smaller sizes.
- Recursion tree
- A diagram of all the calls of a recursive algorithm, used to add up its cost.
- Master theorem
- A rule that gives the solution of recurrences of the form T(n) = aT(n/b) + f(n).
- Fast exponentiation
- Computing a power by squaring half of it, with O(log n) multiplications.
- Maximum subarray
- The run of consecutive elements with the largest total.
- Crossing case
- An answer that spans the boundary between the two halves.
- Kadane's algorithm
- A linear-time method for the maximum subarray problem.
Practice problems
Work each problem on paper first, then reveal the answer to check.
What are the three steps of divide and conquer?
Show answer
Divide, conquer recursively and combine.
What does T(n) = 2T(n/2) + n solve to?
Show answer
O(n log n).
How many multiplications does fast exponentiation need for x¹⁰²⁴?
Show answer
About 11: one squaring for each halving of the exponent, plus one.
Where can the best run of sales be, relative to the middle day?
Show answer
In the left half, in the right half or crossing the middle.
Why must the pieces in divide and conquer be independent?
Show answer
If they overlap, the same work is repeated, as in naive Fibonacci.
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.