Divide and conquer and the master theorem

Introduction

Merge sort, quick sort and binary search all follow one plan, called divide and conquer:

1. Divide the problem into smaller problems of the same kind (usually halves).
2. Conquer each one recursively; a small enough problem is solved directly (the base case).
3. Combine their answers into the answer for the whole.

The skill is in step 3: finding a combine step that is cheap.

You have already used this plan in merge sort, quick sort and binary search. Here you see the plan by itself, apply it to a new problem, and learn how to work out its running time from a formula.

How it works

Example: the best run of numbers

Given numbers that may be negative, find the largest sum of a run of neighbours. In 2 −4 3 −1 2 −6 4 1 it is 4 + 1 = 5. Trying every run is O(n²). Divide and conquer: the best run is either

• entirely in the left half (solve recursively),
• entirely in the right half (solve recursively), or
• crossing the middle: the best run ending at the middle plus the best run starting just after it. Two loops find those in O(n).

#include <stdio.h>

int max3(int a, int b, int c) {
    int m = a > b ? a : b;
    return m > c ? m : c;
}

// The best run that crosses the middle: the best ending at mid, plus the best starting at mid + 1.
int crossing(int a[], int lo, int mid, int hi) {
    int sum = 0, left = a[mid];
    for (int i = mid; i >= lo; i--) {
        sum += a[i];
        if (sum > left) left = sum;
    }
    sum = 0;
    int right = a[mid + 1];
    for (int i = mid + 1; i <= hi; i++) {
        sum += a[i];
        if (sum > right) right = sum;
    }
    return left + right;
}

int best(int a[], int lo, int hi) {
    if (lo == hi) return a[lo];          // one number: it is the best run
    int mid = (lo + hi) / 2;
    return max3(best(a, lo, mid), best(a, mid + 1, hi), crossing(a, lo, mid, hi));
}

int main(void) {
    int a[] = {2, -4, 3, -1, 2, -6, 4, 1};
    printf("best sum: %d\n", best(a, 0, 7));
    return 0;
}

How fast is it? Recurrences

Let T(n) be the time for n items. The program above makes 2 calls of size n/2 and does O(n) extra work:

T(n) = 2 T(n/2) + O(n)

Merge sort has the same recurrence. Draw the recursion as a tree: the top level does n work, the next level two halves of n/2 (n again), and so on, for log₂ n levels. Total: O(n log n).

The master theorem

For T(n) = a T(n/b) + O(n^d), with a calls on problems of size n/b and O(n^d) work to divide and combine, compare a with b^d:

Karatsuba multiplies two n-digit numbers with 3 half-size multiplications instead of 4, and that one saved call turns O(n²) into O(n^1.585). Your computer uses it for very big numbers.

Syntax

T(n) = a T(n/b) + O(n^d)

a     how many recursive calls
n/b   the size of each call
n^d   the work to divide and to combine

Example

To compute x^n, square the answer for n/2: one call of half the size and O(1) work, so T(n) = T(n/2) + O(1) = O(log n) multiplications instead of n.

#include <stdio.h>

int calls = 0;

long long power(long long x, int n) {
    calls++;
    if (n == 0) return 1;
    long long half = power(x, n / 2);     // solve one smaller problem...
    if (n % 2 == 0) return half * half;   // ...and combine it
    return half * half * x;
}

int main(void) {
    printf("3^13 = %lld\n", power(3, 13));
    printf("calls: %d (a simple loop multiplies 13 times)\n", calls);
    return 0;
}

Line by line

1. calls is a global counter, used to see how little work the method does.
2. power adds 1 to calls, and returns 1 when n is 0, which is the base case.
3. half is the answer for n / 2. It is computed once, and used twice.
4. If n is even, x^n is half * half.
5. If n is odd, integer division lost a factor, so one extra x is multiplied in.
6. main prints 3 to the power 13 and the number of calls: 5, because 13, 6, 3, 1 and 0 are each visited once.

Expected result

3^13 = 1594323
calls: 5 (a simple loop multiplies 13 times)

In the real world

Fast multiplication of very large numbers, the fast Fourier transform used throughout signal processing, and the search for the closest pair of points are all divide-and-conquer algorithms. It also suits parallel hardware, because the halves can be worked on at the same time.

Common mistakes

• Using divide and conquer when the smaller problems overlap: fib(n−1) and fib(n−2) solve the same problems again and again. That calls for dynamic programming (memoize).
• A missing or wrong base case, so the recursion never stops.
• An expensive combine step: if combining costs O(n²), the whole method is no faster than brute force.

Best practices

• Find the combine step first, because that is where the idea is.
• Write the recurrence before you code.
• Stop recursing at small sizes in fast code, and use a simple method there.

Summary

Divide and conquer splits a problem, solves the parts recursively and combines the results. The recurrence T(n) = a T(n/b) + O(n^d) describes its cost, and the master theorem usually solves it directly.

Mark lesson complete