Recurrence Relations and Divide-and-Conquer

In Chapter 6 you analysed loops by counting iterations. A recursive method has no loop to count: its cost is defined in terms of itself. The tool for that is a recurrence relation. This chapter shows how to write one, how to solve it, and how to use the answer to design fast divide-and-conquer algorithms.

From recursive code to a recurrence

A recurrence has two parts: the cost of the base case and the cost of the recursive case, written as "the calls it makes + the work it does itself".

static int sum(int[] a, int i) {          // sum of a[i..n-1]
    if (i == a.length) return 0;          // base case: constant work
    return a[i] + sum(a, i + 1);          // one call on a problem of size n-1, plus constant work
}

Trace for a = {4, 7, 1}, calling sum(a, 0). Each call waits for the one below it:

sum(a, 0)                  size 3
  sum(a, 1)                size 2
    sum(a, 2)              size 1
      sum(a, 3)            size 0  -> base case, returns 0
    returns 1 + 0 = 1
  returns 7 + 1 = 8
returns 4 + 8 = 12

Four calls for three elements, each doing a constant amount of work of its own. With n = number of elements still to add: T(0) = c₀ and T(n) = T(n − 1) + c.

Reading rules:

In the code	In the recurrence
each recursive call on a problem of size m	a term T(m)
two calls on halves	2T(n/2)
a loop over the n elements in the method body	+ cn
only constant work outside the calls	+ c

Solving by iteration (unrolling)

Numbers first. Here are three recurrences, computed for small n (empty cells: n/2 is not a whole number):

n	T(n) = T(n/2) + 1, T(1) = 1	T(n) = T(n − 1) + n, T(0) = 0	T(n) = 2T(n − 1) + 1, T(1) = 1
1	1	1	1
2	2	3	3
3		6	7
4	3	10	15
5		15	31
8	4	36	255
16	5	136	65 535

• First column: each doubling of n adds only 1 → it is log₂ n + 1.
• Second column: 1, 3, 6, 10, 15 are the sums 1 + 2 + … + n → n(n + 1)/2.
• Third column: 1, 3, 7, 15, 31 are one less than powers of two → 2ⁿ − 1.

Now the algebra, which confirms each guess.

Substitute the recurrence into itself until you see the pattern, then jump to the base case.

T(n) = T(n − 1) + c = T(n − 2) + 2c = T(n − 3) + 3c = … = T(0) + nc → Θ(n).

T(n) = T(n/2) + c = T(n/4) + 2c = … = T(n/2ᵏ) + kc. The base case is reached when n/2ᵏ = 1, i.e. k = log₂ n, so T(n) = T(1) + c·log₂ n → Θ(log n).

T(n) = T(n − 1) + n = n + (n − 1) + … + 1 + T(0) = n(n + 1)/2 + T(0) → Θ(n²). (The work per level is not constant here: this is the recurrence of selection sort written recursively.)

T(n) = 2T(n − 1) + c: the number of calls doubles at every level, 1 + 2 + 4 + … + 2ⁿ = 2ⁿ⁺¹ − 1 → Θ(2ⁿ). The Towers of Hanoi, T(n) = 2T(n − 1) + 1 with T(1) = 1, gives exactly 2ⁿ − 1 moves.

Substitution: guess and prove

When you have a guess (from unrolling, a tree or experience), prove it by induction. Example: show T(n) = 2T(n/2) + n with T(1) = 1 satisfies T(n) ≤ n log₂ n + n.

Check with numbers first:

n	T(n) = 2T(n/2) + n	n log₂ n + n
1	1	0 + 1 = 1
2	2·1 + 2 = 4	2 + 2 = 4
4	2·4 + 4 = 12	8 + 4 = 12
8	2·12 + 8 = 32	24 + 8 = 32
16	2·32 + 16 = 80	64 + 16 = 80

For powers of two the guess is not just an upper bound, it is exact. Now the proof:

• Base: T(1) = 1 ≤ 1·0 + 1. ✓
• Step: assume it holds for n/2. Then T(n) ≤ 2((n/2) log₂(n/2) + n/2) + n = n(log₂ n − 1) + n + n = n log₂ n + n. ✓

Recursion trees

Draw each call as a node labelled with the work it does outside its recursive calls, then add the costs level by level.

Worked example: T(n) = 2T(n/2) + n with n = 8. Draw it level by level:

level 0:                    [8]                         work 8
                          /     \
level 1:             [4]           [4]                  work 4 + 4 = 8
                    /   \         /   \
level 2:          [2]   [2]     [2]   [2]               work 2+2+2+2 = 8
                  / \   / \     / \   / \
level 3:         1   1 1   1   1   1 1   1              work 8 × 1 = 8
                                                        -----------------
                                              total:    4 levels × 8 = 32

Each level has twice as many nodes, each of half the size, so every level costs the same: 8. There are log₂ 8 + 1 = 4 levels, total 32 — the same value as in the substitution table above.

The same tree in general, for T(n) = 2T(n/2) + cn:

Level	Nodes	Size of each	Work at the level
0	1	n	cn
1	2	n/2	cn
2	4	n/4	cn
…	…	…	…
log₂ n	n	1	cn

Every level costs cn and there are log₂ n + 1 levels: Θ(n log n).

Change one number and see where the work goes (n = 8 again):

Level	2T(n/2) + n²	4T(n/2) + n
0	1 node × 8² = 64	1 node × 8 = 8
1	2 × 4² = 32	4 × 4 = 16
2	4 × 2² = 16	16 × 2 = 32
3	8 × 1² = 8	64 × 1 = 64
total	120 (root is more than half)	120 (leaves are more than half)

The totals happen to be equal here, but the shape is opposite: in the first tree the work shrinks as you go down (the root is the heaviest), in the second it grows (the bottom level is the heaviest). For bigger n this difference decides the answer.

A tree tells you where the work is:

• level costs equal → (cost per level) × (number of levels), e.g. n log n;
• level costs shrinking geometrically (T(n) = 2T(n/2) + n² gives n², n²/2, n²/4, …) → the root dominates, Θ(n²);
• level costs growing geometrically (T(n) = 4T(n/2) + n gives n, 2n, 4n, …) → the leaves dominate. With a = 4 and b = 2 there are a^(log_b n) = n^(log₂ 4) = n² leaves, so Θ(n²).

The Master theorem

For T(n) = aT(n/b) + f(n) with constants a ≥ 1, b > 1, compare f(n) with the number of leaves, n^(log_b a):

Case	Condition	Result	Who dominates
1	f(n) = O(n^(log_b a − ε)) for some ε > 0	Θ(n^(log_b a))	the leaves
2	f(n) = Θ(n^(log_b a))	Θ(n^(log_b a) · log n)	every level equally
3	f(n) = Ω(n^(log_b a + ε)) and a·f(n/b) ≤ k·f(n) for some k < 1	Θ(f(n))	the root

When f(n) = Θ(n^d) the test is just a comparison of a with b^d:

a vs b^d	T(n)
a < b^d	Θ(n^d)
a = b^d	Θ(n^d log n)
a > b^d	Θ(n^(log_b a))

Why a against b^d? Going one level down, the number of calls is multiplied by a, while the work per call is divided by b^d (the size shrinks by b, and the work is size^d). If a is bigger, each level is heavier than the one above; if smaller, lighter; if equal, all levels are the same.

The recipe, in three steps:

1. Read a (number of calls), b (how much the size shrinks) and d (the work outside the calls is n^d; constant work means d = 0).
2. Compute b^d.
3. Compare a with b^d and read the answer from the table.

Recurrence	a	b	d	b^d	Compare	Answer
T(n/2) + 1 (binary search)	1	2	0	1	a = b^d	Θ(log n)
2T(n/2) + n (merge sort)	2	2	1	2	a = b^d	Θ(n log n)
2T(n/2) + 1 (D&C maximum)	2	2	0	1	a > b^d	Θ(n^(log₂ 2)) = Θ(n)
4T(n/2) + n	4	2	1	2	a > b^d	Θ(n^(log₂ 4)) = Θ(n²)
3T(n/2) + n	3	2	1	2	a > b^d	Θ(n^(log₂ 3)) ≈ Θ(n^1.585)
8T(n/2) + n³	8	2	3	8	a = b^d	Θ(n³ log n)
3T(n/4) + n²	3	4	2	16	a < b^d	Θ(n²)
2T(n/2) + n²	2	2	2	4	a < b^d	Θ(n²)

Classic recurrences at a glance

Recurrence	Solution	Typical algorithm
T(n) = T(n − 1) + c	Θ(n)	linear recursion over an array
T(n) = T(n − 1) + cn	Θ(n²)	recursive selection sort
T(n) = T(n/2) + c	Θ(log n)	binary search, fast exponentiation
T(n) = T(n/2) + cn	Θ(n)	work halves each time (geometric series)
T(n) = 2T(n/2) + c	Θ(n)	D&C maximum of an array
T(n) = 2T(n/2) + cn	Θ(n log n)	merge sort, D&C maximum subarray
T(n) = 2T(n − 1) + c	Θ(2ⁿ)	Towers of Hanoi, naive "two calls on n−1"

The divide-and-conquer paradigm

A divide-and-conquer (D&C) algorithm has three steps:

1. Divide the problem into a subproblems of size n/b.
2. Conquer them recursively (small ones are solved directly: the base case).
3. Combine the sub-answers into the answer.

Tiny example: the maximum of {3, 9, 2, 7, 5, 1, 8, 4}. Split in half until one element is left, then combine with Math.max on the way back up:

divide:        [3 9 2 7 5 1 8 4]
              /                 \
        [3 9 2 7]             [5 1 8 4]
         /     \               /     \
     [3 9]   [2 7]         [5 1]   [8 4]

combine:   max(3,9)=9  max(2,7)=7   max(5,1)=5  max(8,4)=8
                max(9,7)=9                max(5,8)=8
                            max(9,8)=9   <- answer

Each combine is one comparison: T(n) = 2T(n/2) + c → Θ(n), no better than a simple loop. D&C only wins when the combine step is clever, as in the examples below.

Its recurrence is T(n) = aT(n/b) + D(n) + C(n), where D and C are the costs of dividing and combining. Designing a fast D&C algorithm is mostly about making the combine step cheap. In merge sort the divide is trivial and the combine (merge) does the work; in quick sort (studied with the other sorting algorithms) the divide (partition) does the work and there is nothing to combine.

Recursive binary search

static int search(int[] a, int key, int lo, int hi) {
    if (lo > hi) return -1;                  // empty range: not found
    int mid = lo + (hi - lo) / 2;            // avoids int overflow of lo + hi
    if (a[mid] == key) return mid;
    if (key < a[mid]) return search(a, key, lo, mid - 1);
    return search(a, key, mid + 1, hi);
}

Trace on a = {3, 8, 15, 21, 30, 42, 57} (indices 0–6):

Call	lo	hi	mid	a[mid]	What happens
key = 42: 1	0	6	3	21	42 > 21 → search right half
key = 42: 2	4	6	5	42	found → return 5
key = 10: 1	0	6	3	21	10 < 21 → search left half
key = 10: 2	0	2	1	8	10 > 8 → search right
key = 10: 3	2	2	2	15	10 < 15 → search left
key = 10: 4	2	1			lo > hi → return −1

One call on half the range plus constant work: T(n) = T(n/2) + c → Θ(log n). For a million elements that is at most 20 calls. It is a decrease-and-conquer algorithm: there is nothing to combine.

Merge sort's recurrence and the merge step

Merge sort splits the array in two halves, sorts each recursively and merges the two sorted halves (the full sorting chapter comes later). The merge walks both halves with two indices and always copies the smaller front element:

static void merge(int[] a, int[] tmp, int lo, int mid, int hi) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi)
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    for (k = lo; k <= hi; k++) a[k] = tmp[k];
}

Trace: merge the left half [1, 4, 7, 8] with the right half [2, 3, 5, 9].

Step	Compare	Take	tmp after the step
1	1 vs 2	1 (left)	[1]
2	4 vs 2	2 (right)	[1, 2]
3	4 vs 3	3 (right)	[1, 2, 3]
4	4 vs 5	4 (left)	[1, 2, 3, 4]
5	7 vs 5	5 (right)	[1, 2, 3, 4, 5]
6	7 vs 9	7 (left)	[1, 2, 3, 4, 5, 7]
7	8 vs 9	8 (left)	[1, 2, 3, 4, 5, 7, 8]
—	left is empty	copy 9	[1, 2, 3, 4, 5, 7, 8, 9]

8 elements, 7 comparisons. Each comparison places one element, so merging n elements costs at most n − 1 comparisons: Θ(n). Hence T(n) = 2T(n/2) + cn → Θ(n log n), in every case (best, average, worst), with Θ(n) extra space for tmp.

The <= (not <) takes the left element on a tie, which keeps equal elements in their original order: merge sort is stable.

Counting inversions

An inversion is a pair of positions i < j with a[i] > a[j]. It measures how unsorted an array is: 0 for a sorted array, n(n − 1)/2 for a reversed one. In [5, 2, 4, 1, 3] there are 7 (5 with 2, 4, 1, 3; 2 with 1; 4 with 1 and 3).

Checking all pairs is Θ(n²). The D&C idea: inversions = (inside the left half) + (inside the right half) + (split inversions: one element in each half). The split ones are counted during the merge: when an element of the right half is copied before the left half is exhausted, it is smaller than every element still waiting on the left, so it forms mid - i + 1 inversions at once.

} else {
    count += mid - i + 1;     // a[j] < a[i], a[i+1], ..., a[mid]
    tmp[k++] = a[j++];
}

Trace on [5, 2, 4, 1, 3] (left half [5, 2, 4], right half [1, 3]):

merge [5] + [2]          2 jumps ahead of 1 waiting element (5)      +1  -> [2, 5]      total 1
merge [2, 5] + [4]       4 jumps ahead of 1 waiting element (5)      +1  -> [2, 4, 5]   total 2
merge [1] + [3]          no jump                                     +0  -> [1, 3]      total 0
merge [2, 4, 5] + [1, 3]:
    1 jumps ahead of 3 waiting elements (2, 4, 5)                    +3
    2 is taken from the left
    3 jumps ahead of 2 waiting elements (4, 5)                       +2  -> [1, 2, 3, 4, 5]
total = 2 (left) + 0 (right) + 5 (split) = 7

The result matches the count by hand. Counting costs nothing extra, so the whole algorithm is still Θ(n log n). Use a long counter: n = 100 000 can already give about 5·10⁹ inversions.

Maximum subarray: divide-and-conquer vs Kadane

Problem: find the largest sum of a contiguous, non-empty block of an array that contains negative numbers. For [2, −5, 3, 1, −2, 4, −6, 1] the answer is 6 (3 + 1 − 2 + 4).

D&C: the best block lies entirely in the left half, entirely in the right half, or crosses the middle. The crossing one is found in Θ(n): extend from mid leftwards keeping the best sum, extend from mid + 1 rightwards keeping the best sum, and add them.

static int maxSub(int[] a, int lo, int hi) {
    if (lo == hi) return a[lo];
    int mid = lo + (hi - lo) / 2;
    int best = Math.max(maxSub(a, lo, mid), maxSub(a, mid + 1, hi));
    int sum = 0, leftBest = Integer.MIN_VALUE;
    for (int i = mid; i >= lo; i--) { sum += a[i]; leftBest = Math.max(leftBest, sum); }
    sum = 0;
    int rightBest = Integer.MIN_VALUE;
    for (int j = mid + 1; j <= hi; j++) { sum += a[j]; rightBest = Math.max(rightBest, sum); }
    return Math.max(best, leftBest + rightBest);
}

Trace of the top call (lo = 0, hi = 7, mid = 3):

index:   0   1   2   3 | 4   5   6   7
value:   2  -5   3   1 |-2   4  -6   1
                     <-mid  mid+1->

Going left from index 3	sum	leftBest
add a[3] = 1	1	1
add a[2] = 3	4	4
add a[1] = −5	−1	4
add a[0] = 2	1	4

Going right from index 4	sum	rightBest
add a[4] = −2	−2	−2
add a[5] = 4	2	2
add a[6] = −6	−4	2
add a[7] = 1	−3	2

Crossing block = 4 + 2 = 6 (indices 2..5). The recursive calls return 4 for the left half (3 + 1) and 4 for the right half (the single 4). Answer: max(4, 4, 6) = 6.

T(n) = 2T(n/2) + cn → Θ(n log n), a clear improvement on the Θ(n²) "try every start and end".

Kadane's algorithm does even better, Θ(n) with one pass: cur is the best sum of a block ending here; either extend the previous block or start again at the current element.

int cur = 0, best = Integer.MIN_VALUE;
for (int x : a) {
    cur = Math.max(x, cur + x);
    best = Math.max(best, cur);
}

x	2	−5	3	1	−2	4	−6	1
cur = max(x, cur + x)	2	−3	3 (restart)	4	2	6	0	1
best	2	2	3	4	4	6	6	6

At x = 3, the old block had sum −3: carrying a debt is worse than starting fresh, so cur restarts at 3.

Fast exponentiation

Computing aⁿ with a loop takes n − 1 multiplications. Squaring halves the exponent: aⁿ = (a^(n/2))² when n is even, and a · (a^(n/2))² when n is odd (with integer division).

static long power(long a, int n) {
    if (n == 0) return 1;
    long half = power(a, n / 2);        // ONE recursive call, stored in a variable
    if (n % 2 == 0) return half * half;
    return a * half * half;
}

Trace of power(3, 13). The calls go down 13 → 6 → 3 → 1 → 0, then the results come back up:

Call	n	half = power(3, n/2)	n even or odd?	Returns
5th	0	—	base case	1
4th	1	1	odd: 3 · 1 · 1	3
3rd	3	3	odd: 3 · 3 · 3	27
2nd	6	27	even: 27 · 27	729
1st	13	729	odd: 3 · 729 · 729	1 594 323

Five calls and at most two multiplications per call, instead of 12 multiplications in a loop.

T(n) = T(n/2) + c → Θ(log n) multiplications: a¹⁰⁰⁰ needs about 10 levels, not 999 multiplications.

For large results, work modulo m and reduce after every multiplication: (x · y) mod m = ((x mod m) · (y mod m)) mod m. Keep m below about 3·10⁹ so that the product of two remainders fits in a long.

Key takeaways

• A recurrence = (calls it makes, each on a smaller size) + (work it does itself). Read it from the code, counting only calls that actually run.
• Compute a few small values first: 1, 2, 3, 4, 5 suggests log n; 1, 3, 6, 10, 15 suggests n²; 1, 3, 7, 15, 31 suggests 2ⁿ.
• Divide by 2 → about log₂ n levels; subtract 1 → n levels. Two calls on n − 1 is exponential; two calls on n/2 is linear plus the combine cost.
• Recursion tree: add the work level by level. Equal levels → (level cost) × (number of levels); shrinking levels → the root wins; growing levels → the leaves win.
• Master theorem for aT(n/b) + n^d: a < b^d → Θ(n^d); a = b^d → Θ(n^d log n); a > b^d → Θ(n^(log_b a)). It does not apply to T(n − 1), to unequal splits, or to the gaps.
• Classic results: binary search Θ(log n), merge sort Θ(n log n), D&C maximum Θ(n), Hanoi Θ(2ⁿ), fast power Θ(log n).
• The merge step is Θ(n) and can count inversions for free (mid - i + 1 each time the right side wins).
• Store the result of one recursive call in a variable: calling it twice can turn Θ(log n) into Θ(n), or Θ(n) into Θ(2ⁿ).