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.

Java Example · Main.java
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");
    }
}
Output
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, labeled 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 recursion tree for merge sort on n elements. The root box says n. It has two children each labeled n over 2, four grandchildren labeled n over 4, and a bottom row of many boxes labeled 1. To the right of each level a total is written: n, n, n, n. A bracket down the side says log base 2 of n levels. At the bottom: total n log n.
The recursion tree for T(n) = 2T(n/2) + n: n work on each of log n levels

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.

Common recurrences and their solutions
RecurrenceExampleSolution
T(n) = T(n/2) + 1Binary searchO(log n)
T(n) = T(n/2) + nQuickselect on average; halving with a linear scanO(n)
T(n) = 2T(n/2) + 1Maximum of an array by halvesO(n)
T(n) = 2T(n/2) + nMerge sort; best run of salesO(n log n)
T(n) = T(n − 1) + nQuicksort with a bad pivot every timeO(n²)
T(n) = 2T(n − 1) + 1Trying both choices for every itemO(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.

Java Example · Main.java
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));
    }
}
Output
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²).

Java Example · Main.java
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);
    }
}
Output
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).

Java Example · Main.java
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 + ")");
    }
}
Output
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.

  1. What are the three steps of divide and conquer?

    Show answer

    Divide, conquer recursively and combine.

  2. What does T(n) = 2T(n/2) + n solve to?

    Show answer

    O(n log n).

  3. How many multiplications does fast exponentiation need for x¹⁰²⁴?

    Show answer

    About 11: one squaring for each halving of the exponent, plus one.

  4. 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.

  5. 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.

Take the quiz