Chapter 19: Solving Recurrence Relations

"Divide each difficulty into as many parts as is feasible and necessary to resolve it." — René Descartes, Discourse on the Method

Overview

In Chapter 14 you learned to put a number on an algorithm's cost: this loop is $\Theta(n)$, that nested pair is $\Theta(n^2)$. The technique there was direct — count the operations, sum the loops. But the fastest algorithms in computing are not loops. They are recursive: merge sort, quicksort, the fast Fourier transform, binary search, Karatsuba multiplication, Strassen's matrix multiplication. Each one solves a problem by breaking it into smaller copies of itself, solving those, and stitching the answers together. When you try to count the operations of such an algorithm, you get something you cannot sum with the methods of Chapter 14, because the cost of the problem is written in terms of the cost of itself on smaller inputs:

$$T(n) = 2\,T(n/2) + n.$$

That is merge sort's running time. The "$2\,T(n/2)$" says I make two recursive calls, each on half the input; the "$+\, n$" says and then I do linear work to merge. This is a recurrence relation, the object you met in Chapter 18. There you learned to model with recurrences and to solve linear recurrences (like Fibonacci's) with the characteristic equation. This chapter is about a different and enormously important family — the divide-and-conquer recurrences — and the single most useful tool in algorithm analysis for solving them: the Master Theorem.

Here is the payoff a programmer gets from this chapter. Right now, if a colleague writes a recursive function and asks "is this fast enough?", you may have to trace it by hand or run it and time it. After this chapter you will be able to look at the recursion, write down its recurrence, and name its running time in seconds — $\Theta(n \log n)$, $\Theta(n^2)$, $\Theta(n^{\log_2 3})$ — without running a line. You will be able to prove that merge sort cannot be slow on any input, that binary search scales to billions of records, and (closing the longest thread in this book) that the Fibonacci numbers, which the naive recursion computes in exponential time, can be computed in $O(\log n)$ time using a trick from linear algebra.

In this chapter, you will learn to:

• Read a recursive algorithm and write its divide-and-conquer recurrence $T(n) = a\,T(n/b) + f(n)$, identifying the branching factor $a$, the shrink factor $b$, and the per-call work $f(n)$.
• Solve such a recurrence with the recursion-tree method, summing the work one level at a time and seeing exactly where the total cost comes from.
• Apply the Master Theorem to classify a recurrence into one of three cases and read off its $\Theta$ bound mechanically.
• Analyze merge sort and binary search from first principles and confirm the answers with the Master Theorem.
• Compute the $n$th Fibonacci number in $O(\log n)$ time by matrix exponentiation, and state its closed form via the golden ratio.
• Recognize the situations where the Master Theorem does not apply and reach for the right alternative.

Learning Paths

🏃 Fast Track: If you have seen the Master Theorem before, skim 19.1 to fix notation, then go straight to 19.3 (the theorem and its three cases) and 19.4 (merge sort and binary search). Do the ⭐⭐ and ⭐⭐⭐ exercises and the matrix-exponentiation material in 19.5 — that part is the Fibonacci payoff and is worth your time even if the rest is review.

📖 Standard Path: Read in order. The recursion tree (19.2) is the intuition the Master Theorem (19.3) compresses into a formula; understand the tree first and the theorem will never feel like a magic incantation. Work every 🔄 Check Your Understanding before moving on.

🔬 Deep Dive: After the chapter, prove the Master Theorem yourself by evaluating the recursion-tree sum as a geometric series in all three regimes (the structure is sketched in 19.3). Then read about the Akra–Bazzi method (19.6), which handles the unequal-split recurrences the Master Theorem cannot.

19.1 Divide-and-conquer recurrences

Let's start with the shape of algorithm this whole chapter is about. Consider how you would search a sorted array for a target value. The slow way scans every element: $\Theta(n)$. The fast way — binary search — looks at the middle element, and based on a single comparison throws away half the array, then repeats on what remains:

def binary_search(arr, target, lo, hi):
    """Return an index of target in sorted arr[lo:hi+1], or -1 if absent."""
    if lo > hi:
        return -1                      # base case: empty range
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)   # search right half
    return binary_search(arr, target, lo, mid - 1)       # search left half

print(binary_search([2, 5, 8, 12, 16, 23, 38], 23, 0, 6))
# Expected output:
# 5

How much work does this do on a range of size $n$? It does a constant amount of work itself — compute a midpoint, one or two comparisons — and then makes one recursive call on a range of size at most $n/2$. If $T(n)$ is the number of operations on a range of size $n$, then

$$T(n) = T(n/2) + c$$

for some constant $c$, with $T(1) = c$ (or whatever the base case costs). This is the canonical pattern of a recursive algorithm that divides the problem, conquers the pieces recursively, and combines the results.

💡 Intuition: Every divide-and-conquer recurrence answers three questions. How many subproblems do I create? (call it $a$). How much smaller is each one? (the input shrinks by a factor $b$, so each subproblem has size $n/b$). How much non-recursive work do I do to split the input and combine the answers? (call it $f(n)$). Binary search: $a=1$ subproblem, size $n/2$ so $b=2$, and $f(n)=c$ constant work. Merge sort: $a=2$ subproblems, $b=2$, and $f(n) = \Theta(n)$ to merge.

We can now write the general form once and for all.

Definition (divide-and-conquer recurrence). A divide-and-conquer algorithm solves a problem of size $n$ by breaking it into $a \ge 1$ subproblems, each of size $n/b$ for some constant $b > 1$, solving each recursively, and doing $f(n)$ additional work to divide the input and combine the results. Its running time satisfies the divide-and-conquer recurrence $$T(n) = a\,T(n/b) + f(n),$$ where $a$ is the number of subproblems (the branching factor), $b$ is the factor by which the input shrinks, and $f(n)$ is the cost of the divide-and-combine work, with a constant base case $T(n) = \Theta(1)$ for $n$ below some threshold.

A few honest technicalities, stated once so they don't trip you later. When $n/b$ is not an integer the real recurrence uses $\lfloor n/b \rfloor$ or $\lceil n/b \rceil$ (you cannot recurse on half of an odd-length array exactly). It is a standard and provable fact — we will not belabor it — that for the recurrences in this chapter, dropping the floors and ceilings does not change the $\Theta$ answer. So we write $T(n/b)$ and analyze the clean version. Likewise we treat the base case as $\Theta(1)$ and don't fuss over its exact value, because it contributes only a constant.

🔗 Connection. In Chapter 14 you analyzed binary search by direct counting: each step halves the range, so after $k$ steps the range has size $n/2^k$, and the search ends when that reaches 1, i.e. when $k = \log_2 n$. That gave $\Theta(\log n)$. That hands-on argument is the solution of $T(n) = T(n/2) + c$ — you solved a recurrence without naming it. This chapter generalizes that one-off argument into machinery that handles any $a$, $b$, and $f$ at once.

Here is the catalog of recurrences we will be able to solve by the end of the chapter, so you can see the territory:

By the end of 19.3 you'll be able to fill in that last column yourself, for any row, in about ten seconds.

🔄 Check Your Understanding 1. For the recurrence $T(n) = 4\,T(n/2) + n^2$, identify $a$, $b$, and $f(n)$. 2. A recursive function makes three calls, each on one-third of the input, and does constant extra work. Write its recurrence. 3. Why does binary search have $a = 1$ but merge sort have $a = 2$, even though both split the input in half?

Answers

1. $a = 4$, $b = 2$, $f(n) = n^2$. 2. $T(n) = 3\,T(n/3) + \Theta(1)$ (here $a = 3$, $b = 3$).
2. Binary search throws away one half and recurses on only the other — it makes a single recursive call ($a=1$). Merge sort must sort both halves, so it makes two recursive calls ($a=2$). The number of recursive calls actually made, not the number of pieces the input is conceptually cut into, is what $a$ counts.

19.2 The recursion-tree method

Before reaching for any theorem, you should be able to solve a divide-and-conquer recurrence by seeing it. The recursion tree is a picture of the recursion that turns the recurrence into a sum you can evaluate. It is also the honest derivation behind the Master Theorem of the next section: the theorem is just this sum, computed once in general.

The idea: draw a node for every call the algorithm makes. The root is the original call on input $n$; it does $f(n)$ work itself (not counting the recursive calls) and has $a$ children, each a call on input $n/b$. Each of those does $f(n/b)$ work and has $a$ children of its own on input $n/b^2$, and so on, until the input shrinks to the base-case size 1. Then you add up the work across the whole tree.

Let's do merge sort's recurrence, $T(n) = 2\,T(n/2) + n$, concretely. Here $a=2$, $b=2$, $f(n)=n$.

Level 0:                        n                         work this level: n
                              /   \
Level 1:               n/2          n/2                   work this level: 2·(n/2) = n
                      /   \        /   \
Level 2:           n/4   n/4    n/4   n/4                 work this level: 4·(n/4) = n
                   ...    ...    ...    ...
Level i:        2^i nodes, each of size n/2^i            work this level: 2^i·(n/2^i) = n
                   ...
Level log2(n):  n leaves, each of size 1                 work this level: n·Θ(1) = Θ(n)

Read down the right-hand column. At level $i$ there are $2^i$ nodes (the tree branches by 2 each level), each handling an input of size $n/2^i$, each doing $f(n/2^i) = n/2^i$ work. So the work at level $i$ is

$$2^i \cdot \frac{n}{2^i} = n.$$

Every level does exactly $n$ work. How many levels are there? The input starts at $n$ and halves each level, reaching 1 at level $\log_2 n$. So there are $\log_2 n + 1$ levels, each costing $n$:

$$T(n) = \sum_{i=0}^{\log_2 n} n = n\,(\log_2 n + 1) = \Theta(n \log n).$$

There is the famous $n \log n$ of merge sort, and now you can see where both factors come from: the $n$ is the work per level, and the $\log n$ is the number of levels. That is a sentence you can say in an interview.

💡 Intuition: A recursion tree has two axes of cost. Across a level: how much total work all the nodes at that depth do. Down the tree: how many levels there are (the height). Multiply, or sum the levels, and you have the total. Three things can happen: the work is the same at every level (merge sort — multiply by the height), the work is dominated by the root (top-heavy), or it is dominated by the leaves (bottom-heavy). Those three outcomes are exactly the three cases of the Master Theorem.

Let's see a top-heavy tree to make the point. Take $T(n) = 2\,T(n/2) + n^2$ ($a=2$, $b=2$, $f(n)=n^2$). Work at level $i$ is

$$2^i \cdot \left(\frac{n}{2^i}\right)^2 = 2^i \cdot \frac{n^2}{4^i} = \frac{n^2}{2^i}.$$

Now the levels are not equal — each level does half the work of the one above. Summing,

$$T(n) = \sum_{i=0}^{\log_2 n} \frac{n^2}{2^i} = n^2 \sum_{i=0}^{\log_2 n} \frac{1}{2^i} < n^2 \sum_{i=0}^{\infty} \frac{1}{2^i} = n^2 \cdot 2 = 2n^2.$$

That sum is a geometric series (Chapter 11), and a decreasing one converges to a constant. So the total is $\Theta(n^2)$ — the root's work, $f(n) = n^2$, dominates, and the recursion below it adds only a constant factor.

🔗 Connection. Everything here rests on geometric series from Chapter 11: $\sum_{i=0}^{\infty} r^i = \frac{1}{1-r}$ for $|r| < 1$, and $\sum_{i=0}^{k} r^i = \frac{r^{k+1}-1}{r-1}$ in general. When the per-level work decreases geometrically (ratio $< 1$), the sum is dominated by its first term (the root). When it increases geometrically (ratio $> 1$), the sum is dominated by its last term (the leaves). When the ratio is exactly 1, every term is equal and the sum is (number of terms) × (term) — that is the $\log n$ factor. The whole Master Theorem is the geometric-series trichotomy in disguise.

Now the general tree, which we'll need in a moment. For $T(n) = a\,T(n/b) + f(n)$:

• Level $i$ has $a^i$ nodes, each on an input of size $n/b^i$.
• Work at level $i$ is $a^i \, f(n/b^i)$.
• The tree has height $\log_b n$ (the input shrinks by $b$ each level until it reaches 1).
• The bottom level has $a^{\log_b n}$ leaves. A little algebra rewrites this exponent: $$a^{\log_b n} = n^{\log_b a}.$$ (Take $\log_b$ of both sides: $\log_b!\left(a^{\log_b n}\right) = (\log_b n)(\log_b a) = \log_b!\left(n^{\log_b a}\right)$.) Each leaf does $\Theta(1)$ work, so the total leaf work is $\Theta(n^{\log_b a})$.

That quantity $n^{\log_b a}$ — the number of leaves — is the hero of the next section. It is the total cost contributed by the bottom of the recursion, and the Master Theorem is, in essence, a contest between it and $f(n)$ (the cost contributed by the top).

🔄 Check Your Understanding 1. For $T(n) = 3\,T(n/2) + n$, how much work is done at level $i$ of the recursion tree? 2. In the same recurrence, is the per-level work increasing or decreasing as you go down? What does that tell you about which part of the tree dominates? 3. Compute $n^{\log_b a}$ for $a = 3$, $b = 2$. (Leave it as a power of $n$.)

Answers

1. There are $3^i$ nodes of size $n/2^i$, each doing $n/2^i$ work, for $3^i \cdot (n/2^i) = n\,(3/2)^i$ work at level $i$. 2. The ratio between consecutive levels is $3/2 > 1$, so the per-level work increases going down — the tree is bottom-heavy and the leaves dominate. 3. $n^{\log_2 3} \approx n^{1.585}$.

19.3 The Master Theorem

The recursion-tree sum, $\sum_{i=0}^{\log_b n} a^i f(n/b^i)$, has the same three behaviors every time, governed by how $f(n)$ compares to the leaf cost $n^{\log_b a}$. The Master Theorem packages those three outcomes so you never have to redo the sum. It is the workhorse of divide-and-conquer analysis, and after a little practice you will apply it in seconds.

🚪 Threshold Concept. The Master Theorem reframes how you read a recursive algorithm. Once you see that the running time of any balanced divide-and-conquer algorithm is decided by a single contest — the work to split-and-combine ($f(n)$) versus the accumulated work at the leaves ($n^{\log_b a}$) — you stop tracing recursions and start classifying them. "Two halves plus linear work" instantly means $n \log n$; "two halves plus constant work" instantly means linear; "more pieces than the shrink can pay for" instantly means leaf-dominated. This single comparison is one of the highest- leverage mental tools in all of algorithm analysis. It is why an experienced engineer can glance at a recursive function and name its complexity without a whiteboard.

Here is the theorem. Recall that $n^{\log_b a}$ is the total work at the leaves; we compare $f(n)$ to it.

The Master Theorem. Let $a \ge 1$ and $b > 1$ be constants, let $f(n)$ be a non-negative function, and let $T(n) = a\,T(n/b) + f(n)$ with a constant base case. Let $E = \log_b a$ (the "critical exponent"). Then:

1. (Leaves win.) If $f(n) = O(n^{E - \varepsilon})$ for some constant $\varepsilon > 0$ — that is, $f$ grows polynomially slower than $n^E$ — then $$T(n) = \Theta\!\left(n^{E}\right) = \Theta\!\left(n^{\log_b a}\right).$$
2. (Tie.) If $f(n) = \Theta(n^{E})$ — that is, $f$ grows at the same rate as $n^E$ — then $$T(n) = \Theta\!\left(n^{E} \log n\right).$$
3. (Root wins.) If $f(n) = \Omega(n^{E + \varepsilon})$ for some constant $\varepsilon > 0$ — that is, $f$ grows polynomially faster than $n^E$ — and the regularity condition $a\,f(n/b) \le c\,f(n)$ holds for some constant $c < 1$ and all large $n$, then $$T(n) = \Theta\!\left(f(n)\right).$$

The strategy for using it. Three steps, every time. (1) Read off $a$, $b$, $f(n)$ from the recurrence. (2) Compute the critical exponent $E = \log_b a$ and the leaf cost $n^E$. (3) Compare $f(n)$ to $n^E$: is $f$ polynomially smaller (Case 1), the same order (Case 2), or polynomially larger (Case 3)? Read the answer from the matching case. The whole method is a single comparison.

Let's drill it on the catalog from 19.1.

Merge sort: $T(n) = 2\,T(n/2) + n$. Here $a=2$, $b=2$, so $E = \log_2 2 = 1$ and $n^E = n^1 = n$. Compare $f(n) = n$ to $n^E = n$: they are the same order, $f(n) = \Theta(n)$. Case 2. Therefore $T(n) = \Theta(n^1 \log n) = \Theta(n \log n)$. ✓ (Matches the recursion tree exactly.)

Binary search: $T(n) = T(n/2) + 1$. Here $a=1$, $b=2$, so $E = \log_2 1 = 0$ and $n^E = n^0 = 1$. Compare $f(n) = 1$ to $n^E = 1$: same order. Case 2. Therefore $T(n) = \Theta(n^0 \log n) = \Theta(\log n)$. ✓

Balanced tree traversal: $T(n) = 2\,T(n/2) + 1$. Here $E = \log_2 2 = 1$, $n^E = n$, and $f(n) = 1$. Is $1$ polynomially smaller than $n$? Yes: $1 = O(n^{1 - \varepsilon})$ for, say, $\varepsilon = 1$ (then $n^{1-\varepsilon} = n^0 = 1$, and $1 = O(1)$). Case 1. Therefore $T(n) = \Theta(n^1) = \Theta(n)$. That is why visiting every node of a balanced binary tree is linear: there are $\Theta(n)$ nodes and you do constant work at each.

Karatsuba multiplication: $T(n) = 3\,T(n/2) + n$. Here $a=3$, $b=2$, so $E = \log_2 3 \approx 1.585$ and $n^E = n^{\log_2 3}$. Compare $f(n) = n = n^1$ to $n^{1.585}$: $f$ is polynomially smaller (take $\varepsilon = 0.5$, say, and $n = O(n^{1.085})$). Case 1. Therefore $T(n) = \Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$ — which famously beats the $\Theta(n^2)$ of grade-school multiplication, and is why Karatsuba's trick (replacing four half-size multiplications with three) is worth the extra additions.

A Case 3 example: $T(n) = 2\,T(n/2) + n^2$. Here $E = \log_2 2 = 1$, $n^E = n$, and $f(n) = n^2$ is polynomially larger than $n$ ($n^2 = \Omega(n^{1 + \varepsilon})$ with $\varepsilon = 1$). We must also check regularity: $a\,f(n/b) = 2\,(n/2)^2 = 2 \cdot \frac{n^2}{4} = \frac{n^2}{2} = \frac{1}{2} f(n)$, so $c = \frac{1}{2} < 1$ works. Case 3. Therefore $T(n) = \Theta(f(n)) = \Theta(n^2)$. ✓ (Matches the top-heavy tree in 19.2.)

⚠️ Common Pitfall: "polynomially" smaller or larger is not the same as "smaller or larger." The gap between $f(n)$ and $n^E$ in Cases 1 and 3 must be at least a factor of $n^{\varepsilon}$ for some fixed $\varepsilon > 0$. A merely logarithmic gap is not enough, and it lands you in the theorem's blind spot. For example, $T(n) = 2\,T(n/2) + n\log n$ has $E = 1$, $n^E = n$, and $f(n) = n\log n$. Is $n\log n$ polynomially larger than $n$? No — $\frac{n\log n}{n} = \log n$ grows slower than every $n^{\varepsilon}$, so there is no valid $\varepsilon$. This recurrence falls between Cases 2 and 3 and the Master Theorem (as stated) says nothing. (We'll resolve it in 19.6; the answer is $\Theta(n \log^2 n)$.)

It is worth knowing why the theorem is true, because the reason is exactly the recursion-tree sum from 19.2. The total cost is $T(n) = \sum_{i=0}^{\log_b n} a^i f(n/b^i)$, a sum whose terms form (essentially) a geometric series with ratio governed by $f$ versus $n^E$. If $f$ is small (Case 1) the terms grow geometrically toward the leaves, so the sum is dominated by its last term, $n^{\log_b a}$ — the leaf work. If $f$ is large (Case 3) the terms shrink geometrically away from the root, so the sum is dominated by its first term, $f(n)$ — the root's work (regularity is what guarantees the shrinkage). If $f$ matches $n^E$ (Case 2) every term is the same order, and there are $\Theta(\log n)$ of them, giving the extra $\log n$ factor. That is the whole proof in one paragraph; the Deep Dive path asks you to make each regime rigorous.

🔄 Check Your Understanding 1. Apply the Master Theorem to $T(n) = 4\,T(n/2) + n$. (Find $E$, classify, give the answer.) 2. Apply it to $T(n) = 2\,T(n/2) + n^3$. Don't forget the regularity check. 3. A student claims the Master Theorem gives $T(n) = T(n/2) + n$ a bound of $\Theta(n \log n)$. Are they right? Work it out.

Answers

1. $a=4, b=2 \Rightarrow E = \log_2 4 = 2$, $n^E = n^2$. Compare $f(n) = n$ to $n^2$: $f$ is polynomially smaller, Case 1, so $T(n) = \Theta(n^2)$. 2. $a=2, b=2 \Rightarrow E = 1$, $n^E = n$; $f(n) = n^3 = \Omega(n^{1+\varepsilon})$ (Case 3 candidate). Regularity: $2(n/2)^3 = 2 \cdot \frac{n^3}{8} = \frac{n^3}{4} = \frac{1}{4} f(n)$, so $c = 1/4 < 1$ holds. **Case 3**, $T(n) = \Theta(n^3)$. 3. No. Here $a=1, b=2 \Rightarrow E = \log_2 1 = 0$, $n^E = 1$, and $f(n) = n$ is polynomially larger than $1$. Regularity: $1 \cdot f(n/2) = n/2 = \frac{1}{2}f(n)$, $c = 1/2 < 1$. So this is Case 3, and $T(n) = \Theta(n)$, not $\Theta(n\log n)$. (The student confused it with the merge-sort Case-2 pattern.)

19.4 Merge sort and binary search, analyzed

We have used merge sort and binary search as examples; now let's analyze them properly — derive the recurrence from the code, solve it, and (for merge sort) prove that the bound holds in the worst case, not just on lucky inputs. This is the section where the machinery earns its keep on real algorithms.

Merge sort, from code to closed form

Merge sort sorts a list by splitting it in half, recursively sorting each half, and merging the two sorted halves into one:

def merge_sort(a):
    """Return a new sorted list. T(n) = 2 T(n/2) + Theta(n)."""
    if len(a) <= 1:
        return a[:]                       # base case: already sorted
    mid = len(a) // 2
    left = merge_sort(a[:mid])            # sort first half
    right = merge_sort(a[mid:])           # sort second half
    return merge(left, right)             # combine in linear time

def merge(left, right):
    """Merge two sorted lists into one sorted list, in Theta(len) time."""
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:]); out.extend(right[j:])
    return out

print(merge_sort([5, 2, 8, 1, 6, 3, 7, 4]))
# Expected output:
# [1, 2, 3, 4, 5, 6, 7, 8]

Read off the recurrence. The function makes two recursive calls ($a = 2$), each on half the list ($b = 2$). The non-recursive work is the split (slicing, $\Theta(n)$) plus the merge. The merge does a constant amount of work per element appended and appends all $n$ elements exactly once, so it is $\Theta(n)$. Total non-recursive work: $f(n) = \Theta(n)$. Hence

$$T(n) = 2\,T(n/2) + \Theta(n).$$

We solved this twice already — recursion tree (19.2) and Master Theorem Case 2 (19.3) — and both give $T(n) = \Theta(n \log n)$.

But notice something important: this bound holds regardless of the input's contents. The split always produces two halves; the merge always touches all $n$ elements no matter how they were arranged. There is no "lucky" input that makes merge sort faster and no "unlucky" one that makes it slower by more than a constant. So merge sort is $\Theta(n \log n)$ in the best, worst, and average case alike — a guarantee that, say, quicksort (whose worst case is $\Theta(n^2)$) cannot make.

The strategy first (the merge is correct and linear). We claim merge produces a sorted list and runs in $\Theta(n)$ time, where $n = $ len(left) $+$ len(right). The idea: each pass of the loop appends exactly one element and advances exactly one of the two pointers, so after at most $n$ passes both lists are exhausted; and the smallest unappended element is always at one of the two pointers, so the output comes out sorted. We prove the linear-time half rigorously (the sortedness is an exercise in loop invariants from Chapter 6).

Claim. merge(left, right) performs $\Theta(n)$ operations, where $n$ is the total number of elements.

Proof. Let $n = \lvert \text{left} \rvert + \lvert \text{right} \rvert$. Consider the quantity $i + j$, the sum of the two indices. It starts at $0$. Each iteration of the while loop appends one element and increments exactly one of $i$ or $j$, so each iteration increases $i + j$ by exactly $1$ and does $\Theta(1)$ work. The loop continues only while $i < \lvert \text{left} \rvert$ and $j < \lvert \text{right} \rvert$, so it stops once $i + j$ can no longer be increased without exceeding a bound — certainly by the time $i + j = n$. Hence the loop runs at most $n$ times, doing $\Theta(n)$ total work. The two extend calls afterward together append the remaining elements, at most $n$ of them, in $\Theta(n)$ time. The total is $\Theta(n) + \Theta(n) = \Theta(n)$. $\blacksquare$

With the merge confirmed linear, the recurrence $T(n) = 2T(n/2) + \Theta(n)$ is justified, and merge sort's $\Theta(n \log n)$ worst-case bound follows. This is the first time in the book we have proved the running time of a real sorting algorithm — exactly the promise Chapter 14 made when it deferred "$\Theta(n\log n)$ of merge sort" to this chapter.

🔗 Connection. In Chapter 14 you learned the growth hierarchy and saw that $\Theta(n \log n)$ sits just above linear and far below $\Theta(n^2)$. You also learned (in the lower-bound discussion) that no comparison sort can beat $\Theta(n \log n)$ in the worst case. Merge sort therefore matches the lower bound — it is asymptotically optimal among comparison sorts. The recurrence we just solved is the upper-bound half of that optimality story.

Binary search, formally

We derived binary search's recurrence in 19.1: $T(n) = T(n/2) + \Theta(1)$, because each call does constant work and makes one recursive call on (at most) half the range. By the Master Theorem (Case 2, with $E = \log_2 1 = 0$), $T(n) = \Theta(\log n)$.

Worth pausing on what $\Theta(\log n)$ buys you. On a sorted array of one billion ($10^9$) elements, linear search may probe up to a billion entries; binary search probes at most $\lceil \log_2 10^9 \rceil = 30$. That is the difference between an operation you can do a million times a second and one you can do thirty million times total in the same wall-clock budget. The logarithm is the reason every database index, every std::map, and every "find in sorted data" routine is built on halving.

🔄 Check Your Understanding 1. Merge sort's $\Theta(n \log n)$ holds in the worst case. Name one concrete reason it cannot have a worse (slower) case, the way quicksort does. 2. Suppose you "improve" merge sort to split the list into three parts and recurse on all three, merging in $\Theta(n)$. Write the new recurrence and solve it. Is it asymptotically faster? 3. If binary search recursed on both halves instead of one (a silly bug), what would its recurrence and running time become?

Answers

1. The amount of work merge sort does is independent of the data's arrangement: the split is always into halves and the merge always touches every element exactly once. There is no input that forces an unbalanced split (the way a bad pivot does in quicksort), so the recurrence — and the bound — is the same for every input. 2. $T(n) = 3\,T(n/3) + \Theta(n)$: $a=3, b=3 \Rightarrow E = \log_3 3 = 1$, $f(n) = \Theta(n) = \Theta(n^E)$, Case 2, so $T(n) = \Theta(n \log n)$ — the same as two-way merge sort. Splitting into more parts changes the base of the logarithm (a constant factor), not the asymptotic class. 3. $T(n) = 2\,T(n/2) + \Theta(1)$, which is Case 1 with $E = 1$, giving $\Theta(n)$ — the bug throws away binary search's entire advantage and makes it as slow as a linear scan.

19.5 Fibonacci in $O(\log n)$: matrix exponentiation

Now the chapter's anchor payoff, and one of the most satisfying results in the book. The Fibonacci numbers have followed us since Chapter 6, where they were defined recursively and proven about by induction; through Chapter 7's strong induction; through Chapter 11 as a sequence; and through Chapter 18, where you solved their recurrence in closed form using the characteristic equation. We restate that closed form, then show something the closed form does not immediately give us: how to compute $F_n$ for enormous $n$ in only $O(\log n)$ arithmetic operations.

The naive recursion is exponential

Recall $F_0 = 0$, $F_1 = 1$, $F_n = F_{n-1} + F_{n-2}$. The direct translation into code is the textbook example of an accidentally exponential algorithm:

def fib_naive(n):
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

What is its running time? Each call makes two calls, on $n-1$ and $n-2$. The count of operations $T(n)$ satisfies $T(n) = T(n-1) + T(n-2) + \Theta(1)$ — itself a Fibonacci-like recurrence! Its solution grows like $F_n$ itself, which (by the closed form below) is $\Theta(\phi^n)$ where $\phi \approx 1.618$. So fib_naive(50) already triggers on the order of $\phi^{50} \approx 10^{10}$ calls. This is not a divide-and-conquer recurrence — the subproblems shrink by a subtraction ($n-1$), not a division ($n/b$) — so the Master Theorem does not apply (a preview of 19.6). It is exponential because it recomputes the same subproblems an exponential number of times.

⚠️ Common Pitfall: The naive Fibonacci is the canonical warning that recursion is not free. The recursion tree here is not balanced and does not shrink by a constant factor per level; it has $\Theta(\phi^n)$ nodes because identical subproblems are solved over and over. The fix programmers reach for first is memoization (cache each $F_k$), which brings it to $\Theta(n)$ — linear, because each of $F_0, \dots, F_n$ is computed once. That is already a vast improvement. But we can do dramatically better: $O(\log n)$.

The matrix that generates Fibonacci

The key observation is that one step of the Fibonacci recurrence is a linear transformation, and linear transformations are matrices. Stack two consecutive Fibonacci numbers into a vector and watch one step of the recurrence:

$$\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n} \\ F_{n-1} \end{pmatrix}.$$

Check the arithmetic: the top row gives $F_{n+1} = 1 \cdot F_n + 1 \cdot F_{n-1}$ (the recurrence exactly), and the bottom row gives $F_n = 1 \cdot F_n + 0 \cdot F_{n-1}$ (a trivially true bookkeeping identity that shifts the window down). Call that matrix $M = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}$. Applying $M$ once advances the Fibonacci window by one step. Applying it $n$ times advances it $n$ steps from the start:

$$\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = M^n \begin{pmatrix} F_1 \\ F_0 \end{pmatrix} = M^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}.$$

Even cleaner is the closed matrix identity, which we can prove by induction.

Claim. For all integers $n \ge 1$, $$M^n = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n} = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}.$$

The strategy first. This is a statement about every $n \ge 1$, so induction is the natural tool (Chapter 6). The base case is a direct check of $M^1$. The inductive step uses $M^{k+1} = M^k \cdot M$, substitutes the inductive hypothesis for $M^k$, multiplies the two matrices, and recognizes each resulting entry as a Fibonacci number via the defining recurrence $F_{j+1} = F_j + F_{j-1}$. This is the same "use the recurrence to recombine terms" move you saw in Chapter 6's Fibonacci-sum proof.

Proof (by induction on $n$). Let $P(n)$ be the matrix identity above.

Base case ($n = 1$): the right side is $\begin{pmatrix} F_2 & F_1 \ F_1 & F_0 \end{pmatrix} = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}$, since $F_2 = 1$, $F_1 = 1$, $F_0 = 0$. This is exactly $M^1$. So $P(1)$ holds.

Inductive step: fix $k \ge 1$ and assume $P(k)$, i.e. $M^k = \begin{pmatrix} F_{k+1} & F_k \ F_k & F_{k-1} \end{pmatrix}$. Then $$M^{k+1} = M^k \cdot M = \begin{pmatrix} F_{k+1} & F_k \\ F_k & F_{k-1} \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} F_{k+1} + F_k & F_{k+1} \\ F_k + F_{k-1} & F_k \end{pmatrix}.$$ By the Fibonacci recurrence, $F_{k+1} + F_k = F_{k+2}$ and $F_k + F_{k-1} = F_{k+1}$, so the right side equals $\begin{pmatrix} F_{k+2} & F_{k+1} \\ F_{k+1} & F_k \end{pmatrix}$, which is exactly $P(k+1)$. By induction, $P(n)$ holds for all $n \ge 1$. $\blacksquare$

So $F_n$ is simply the top-right (or bottom-left) entry of $M^n$. Computing $F_n$ has become computing a matrix power. And matrix powers can be computed astonishingly fast.

Fast exponentiation: $O(\log n)$ multiplications

To compute $M^n$, you do not multiply $M$ by itself $n$ times — that would be $\Theta(n)$ multiplications, no better than the linear memoized version. Instead use exponentiation by squaring, which exploits the identities

$$M^n = \begin{cases} \left(M^{n/2}\right)^2 & n \text{ even}, \\ M \cdot \left(M^{(n-1)/2}\right)^2 & n \text{ odd}. \end{cases}$$

Each step halves the exponent at the cost of one squaring (and possibly one extra multiply). Halving $n$ until it reaches 0 takes $\Theta(\log n)$ steps, so the whole computation is $O(\log n)$ matrix multiplications. Each multiplication of $2 \times 2$ matrices is a constant number of integer operations, so — counting an integer multiplication as one operation — computing $F_n$ takes $O(\log n)$ operations. From $\Theta(\phi^n)$ down to $O(\log n)$: that is the arc of this chapter.

💡 Intuition: Exponentiation by squaring is itself a divide-and-conquer algorithm, and its recurrence is $T(n) = T(n/2) + \Theta(1)$ — the same as binary search! (Here $n$ is the exponent.) Master Theorem Case 2 gives $\Theta(\log n)$. So the Fibonacci speedup is binary search's logarithm wearing a different hat: each squaring doubles the "reach" of the exponent, just as each comparison halves the search range.

Here is the algorithm in code:

def mat_mult(A, B):
    """Multiply two 2x2 matrices given as ((a,b),(c,d))."""
    (a, b), (c, d) = A
    (e, f), (g, h) = B
    return ((a*e + b*g, a*f + b*h),
            (c*e + d*g, c*f + d*h))

def fib_fast(n):
    """nth Fibonacci via matrix exponentiation, O(log n) multiplications."""
    result = ((1, 0), (0, 1))            # identity matrix
    base = ((1, 1), (1, 0))              # M
    while n > 0:
        if n & 1:                        # if current bit is set, fold in base
            result = mat_mult(result, base)
        base = mat_mult(base, base)      # square: M, M^2, M^4, M^8, ...
        n >>= 1                          # move to next bit of n
    return result[0][1]                  # top-right entry is F_n

print(fib_fast(10))
# Expected output:
# 55

Let's hand-trace fib_fast(10) to be sure (and because tracing is how you reason about output without running it). The exponent $10 = 1010_2$, so its bits from least significant are $0, 1, 0, 1$.

After the loop, result $= M^{10} = \begin{pmatrix} F_{11} & F_{10} \\ F_{10} & F_{9} \end{pmatrix}$, and result[0][1] $= F_{10} = 55$. The loop ran 4 times — $\lfloor \log_2 10 \rfloor + 1 = 4$ — confirming the $O(\log n)$ count. (Indeed $M^{10} = \begin{pmatrix} 89 & 55 \\ 55 & 34 \end{pmatrix}$, and $F_{11} = 89$, $F_{10} = 55$, $F_9 = 34$.)

The closed form, restated (the golden ratio)

For completeness, recall the closed form you derived in Chapter 18 by solving Fibonacci's characteristic equation $x^2 = x + 1$. Its two roots are the golden ratio $\phi = \frac{1 + \sqrt{5}}{2} \approx 1.618$ and its conjugate $\psi = \frac{1 - \sqrt{5}}{2} \approx -0.618$, and the closed form (Binet's formula) is

$$F_n = \frac{\phi^{\,n} - \psi^{\,n}}{\sqrt{5}}.$$

Because $\lvert \psi \rvert < 1$, the term $\psi^n$ shrinks to nothing, and $F_n$ is the nearest integer to $\frac{\phi^n}{\sqrt 5}$. This is beautiful and it confirms the growth rate $F_n = \Theta(\phi^n)$ that explained the naive recursion's exponential blowup. But notice: as a computational method it is treacherous, because $\phi^n$ is irrational and floating-point rounding error grows with $n$, giving wrong integers for large $n$. The matrix method uses only integer arithmetic and is exact for every $n$. So we have two complementary results: the closed form tells us how fast Fibonacci grows; matrix exponentiation tells us how to compute it fast and exactly.

🔗 Connection. This is theme four of the book in one example. The closed form (a proof-flavored result) settles the asymptotic growth for all $n$ at once. The matrix algorithm (a computational result) gives an exact, fast procedure. Neither replaces the other: you would prove $F_n = \Theta(\phi^n)$ with the closed form, but *compute* $F_{1000000}$ with the matrix method. Chapter 23's fast modular exponentiation, which powers RSA, is exactly this same squaring trick applied to numbers instead of matrices — you are learning the engine of public-key cryptography here, one chapter early.

🔄 Check Your Understanding 1. Why is the naive recursive Fibonacci exponential while the matrix method is logarithmic, even though both compute the same numbers? 2. In fib_fast, how many times does the while loop run for $n = 16$? For $n = 17$? 3. Why is Binet's closed form a poor computational method for large $n$, despite being exact in principle?

Answers

1. The naive version re-solves identical subproblems an exponential number of times (its call tree has $\Theta(\phi^n)$ nodes). The matrix method computes $M^n$ by squaring, halving the exponent each step, so it does only $O(\log n)$ multiplications and never recomputes anything. 2. For $n = 16 = 10000_2$ the loop runs $\lfloor \log_2 16 \rfloor + 1 = 5$ times; for $n = 17 = 10001_2$ it also runs 5 times (both have a highest set bit at position 4). 3. $\phi^n$ is irrational, so a computer must approximate it in floating point; the rounding error grows with $n$ and eventually flips the nearest-integer rounding, producing a wrong Fibonacci number. The matrix method uses exact integer arithmetic and stays correct for every $n$.

19.6 When the Master Theorem fails

The Master Theorem is powerful but not universal. Knowing its boundaries is as important as knowing its cases — reaching for it on a recurrence it cannot handle is a real and common error. Here are the situations where it does not apply, and what to do instead.

1. Subtractive recurrences (the subproblems shrink by subtraction, not division). The Master Theorem requires the form $a\,T(n/b) + f(n)$ — subproblems of size $n/b$. The naive Fibonacci recurrence $T(n) = T(n-1) + T(n-2) + \Theta(1)$ shrinks by subtracting, so the theorem simply does not apply. Such recurrences are the linear recurrences of Chapter 18, solved by the characteristic equation, or analyzed by other means. (A recurrence like $T(n) = T(n-1) + \Theta(n)$ unrolls to $\sum_{k=1}^{n} \Theta(k) = \Theta(n^2)$ — that is the recurrence behind insertion sort and selection sort.)

2. The gap between $f(n)$ and $n^E$ is only logarithmic (the Case 2/3 blind spot). We met this in 19.3: $T(n) = 2\,T(n/2) + n \log n$. Here $E = 1$ and $f(n) = n\log n$, which is larger than $n^1$ but not polynomially larger (the ratio $\log n$ beats no $n^\varepsilon$). The three cases as stated have a gap here. The fix is the recursion tree: each of the $\log n$ levels does $\Theta(n \log n)$ work (you can check the per-level work stays $\Theta(n \log n)$ down the tree), giving $\Theta(n \log^2 n)$. There is also an extended Master Theorem (sometimes Case 2 with a parameter $k$) stating that $T(n) = a\,T(n/b) + \Theta(n^E \log^k n)$ solves to $\Theta(n^E \log^{k+1} n)$ — apply it with $E = 1$, $k = 1$ to get $\Theta(n \log^2 n)$ directly.

3. Unequal subproblem sizes. The Master Theorem assumes every subproblem has the same size $n/b$. An algorithm that recurses on, say, sizes $n/3$ and $2n/3$ produces $T(n) = T(n/3) + T(2n/3) + \Theta(n)$, which the theorem cannot touch. The right tool is the Akra–Bazzi method, a generalization that handles $T(n) = \sum_i a_i T(n/b_i) + f(n)$ with different $b_i$. (This particular recurrence solves to $\Theta(n \log n)$, and it is the recurrence behind the worst case of well-balanced quicksort-style partitioning.)

4. A non-constant or non-polynomial $f(n)$, or non-constant $a$ or $b$. The theorem requires $a, b$ constant and $f$ a reasonably behaved (typically polynomial or poly-log) function. Exotic $f$ — say $f(n) = n / \log n$ — can fall outside all three cases and needs the recursion tree or substitution.

💡 Intuition: The recursion-tree method (19.2) is the universal tool; the Master Theorem is the fast shortcut for the common case. Whenever the theorem stalls — subtraction instead of division, a logarithmic gap, unequal splits, a strange $f$ — fall back to drawing the tree and summing the levels as a series. The tree never fails; it just costs you more arithmetic than the theorem when the theorem applies.

The other classical fallback is the substitution method: guess the answer (often by drawing a tree), then prove it by induction, exactly as in Chapter 6 — assume the bound for inputs smaller than $n$, plug into the recurrence, and verify it holds at $n$. Substitution is the rigorous backstop for any recurrence whose form defeats the Master Theorem, and it is the standard way to prove a guessed bound correct.

🐛 Find the Error. A student analyzes $T(n) = 2\,T(n/2) + n^2$ and reasons: "$f(n) = n^2$ is bigger than $n^E = n$, so it's Case 3, and $T(n) = \Theta(f(n)) = \Theta(n^2)$. Done." Their answer happens to be right, but their reasoning skipped something the theorem requires. What did they forget, and why does it matter here even though the conclusion is correct?

Answer

They forgot to check the regularity condition $a\,f(n/b) \le c\,f(n)$ for some $c < 1$. Case 3 is not licensed by "$f$ is polynomially larger" alone — you must also verify that $f$ does not misbehave as it recurses. Here it does hold ($2(n/2)^2 = \frac{n^2}{2} = \frac{1}{2}f(n)$, so $c = \frac{1}{2}$), so the answer stands — but the student got lucky by omitting a step that is necessary in general. There are functions that are polynomially larger than $n^E$ yet violate regularity (pathological, oscillating $f$), and for those, skipping the check gives a wrong answer. Always check regularity before invoking Case 3.

Project Checkpoint: fast Fibonacci for the Toolkit

In Chapter 18 you added solve_linear(coeffs, inits, n) to dmtoolkit/recurrences.py — a general solver for linear recurrences. Now we complete that module's headline function: fib(n), computing the $n$th Fibonacci number in $O(\log n)$ time by the matrix exponentiation we developed in 19.5. This is the canonical signature from the Toolkit API, and it is the function the capstone's RSA work (Chapter 25) will echo when it needs fast modular exponentiation.

Add the following to dmtoolkit/recurrences.py:

def _mat_mult(A, B):
    """Multiply two 2x2 matrices represented as ((a, b), (c, d))."""
    (a, b), (c, d) = A
    (e, f), (g, h) = B
    return ((a*e + b*g, a*f + b*h),
            (c*e + d*g, c*f + d*h))

def fib(n):
    """Return the nth Fibonacci number (F_0 = 0, F_1 = 1) in O(log n) time
    using matrix exponentiation of M = [[1,1],[1,0]]. Exact integer arithmetic."""
    if n < 0:
        raise ValueError("fib(n) is defined for n >= 0")
    result = ((1, 0), (0, 1))            # identity (M^0)
    base = ((1, 1), (1, 0))              # M
    while n > 0:
        if n & 1:
            result = _mat_mult(result, base)
        base = _mat_mult(base, base)     # M, M^2, M^4, M^8, ...
        n >>= 1
    return result[0][1]                  # top-right entry equals F_n

print([fib(k) for k in range(10)])
# Expected output:
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

The expected output is the first ten Fibonacci numbers, hand-verified: $F_0$ through $F_9$ are $0,1,1,2,3,5,8,13,21,34$. (We traced fib(10) = 55 step by step in 19.5; the same loop, run for each $k < 10$, produces this list.)

How it builds toward the capstone. Two ways. First, this fib(n) is the fast, exact engine that replaces the exponential fib_naive from Chapter 6 — the same function, now $O(\log n)$ — closing the Fibonacci thread the book has carried since Part I. Second, and more importantly for the capstone, the technique is exponentiation by squaring, and in Chapter 23 you will reuse exactly this halving loop on integers modulo $n$ to build mod_pow(b, e, m) — the operation that makes RSA encryption and decryption fast enough to be practical. When you implement RSA in the Chapter 25 capstone track, the $O(\log e)$ modular-exponentiation loop you write will be this same loop with integer multiplication replaced by modular multiplication. You are building the cryptographic engine one chapter early, in the friendlier setting of matrices.

Toolkit so far: logic.py (Ch. 1–3), sets.py (Ch. 8), relations.py (Ch. 12–13), combinatorics.py (Ch. 15–17), and now recurrences.py complete with solve_linear (Ch. 18) and a logarithmic fib (this chapter). Next come the probability and number-theory modules — and the squaring trick returns in force.

Summary

A divide-and-conquer recurrence has the form $T(n) = a\,T(n/b) + f(n)$: $a$ subproblems, each of size $n/b$, plus $f(n)$ split-and-combine work. This chapter's tools for solving it:

The recursion-tree method (always works). For $T(n) = a\,T(n/b) + f(n)$:

The Master Theorem (the fast shortcut). Let $E = \log_b a$ and compare $f(n)$ to $n^E$:

Worked recurrences to memorize:

Fibonacci, the anchor:

• Naive recursion: $T(n) = T(n-1) + T(n-2) + \Theta(1)$, solution $\Theta(\phi^n)$ — exponential (subtractive, not a Master-Theorem recurrence).
• Memoized: $\Theta(n)$. Matrix exponentiation: $O(\log n)$, via $M = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}$ and $M^n = \begin{pmatrix} F_{n+1} & F_n \ F_n & F_{n-1} \end{pmatrix}$ (proved by induction), computed by exponentiation by squaring.
• Closed form (Binet): $F_n = \dfrac{\phi^n - \psi^n}{\sqrt 5}$, $\phi = \frac{1+\sqrt 5}{2}$, $\psi = \frac{1-\sqrt 5}{2}$ — exact in symbols, but rounding-unsafe to compute; use the matrix method for exact values.

When the Master Theorem does not apply: subtractive recurrences (use the characteristic equation or unrolling); a merely logarithmic gap between $f$ and $n^E$ (use the recursion tree or the extended Case 2: $\Theta(n^E \log^k n) \to \Theta(n^E \log^{k+1} n)$); unequal subproblem sizes (Akra–Bazzi); a pathological $f$ (recursion tree or substitution). The substitution method — guess, then prove by induction (Chapter 6) — is the universal rigorous backstop.

Spaced Review

Retrieval keeps knowledge available. Answer from memory before checking.

1. (Ch. 18) What is the characteristic equation of the Fibonacci recurrence $F_n = F_{n-1} + F_{n-2}$, and what are its two roots? How do those roots relate to this chapter's closed form?
2. (Ch. 18) Distinguish a linear homogeneous recurrence from a divide-and-conquer recurrence. Which kind is $T(n) = 2T(n/2) + n$, and which kind is $F_n = F_{n-1} + F_{n-2}$?
3. (Ch. 14) State the formal definition of $f(n) = \Theta(g(n))$. In which Master-Theorem case does $f(n) = \Theta(n^{\log_b a})$ put a recurrence?
4. (Ch. 14) Order these from slowest- to fastest-growing: $\Theta(n^2)$, $\Theta(n \log n)$, $\Theta(\log n)$, $\Theta(n^{\log_2 3})$, $\Theta(n)$. Which one is merge sort, and which is Karatsuba?

Answers

1. The characteristic equation is $x^2 = x + 1$, i.e. $x^2 - x - 1 = 0$, with roots $\phi = \frac{1+\sqrt 5}{2}$ and $\psi = \frac{1-\sqrt 5}{2}$. The closed form is $F_n = \frac{\phi^n - \psi^n}{\sqrt 5}$ — built directly from those two roots (the general solution of a linear homogeneous recurrence is a combination of powers of the characteristic roots). 2. A linear homogeneous recurrence expresses $a_n$ as a fixed linear combination of earlier terms ($a_{n-1}, a_{n-2}, \dots$) with the index decreasing by subtraction; a divide-and-conquer recurrence expresses $T(n)$ in terms of $T$ at divided inputs ($n/b$) plus extra work. $T(n) = 2T(n/2) + n$ is divide-and-conquer; $F_n = F_{n-1} + F_{n-2}$ is linear homogeneous. 3. $f(n) = \Theta(g(n))$ means there are constants $c_1, c_2 > 0$ and $n_0$ with $c_1 g(n) \le f(n) \le c_2 g(n)$ for all $n \ge n_0$. If $f(n) = \Theta(n^{\log_b a})$ it is Case 2 ($\Theta(n^{\log_b a}\log n)$). 4. Slowest to fastest: $\Theta(\log n) < \Theta(n) < \Theta(n \log n) < \Theta(n^{\log_2 3}) < \Theta(n^2)$ (note $n^{\log_2 3} \approx n^{1.585}$ sits between $n\log n$ and $n^2$). Merge sort is $\Theta(n \log n)$; Karatsuba is $\Theta(n^{\log_2 3})$.

What's Next

You have now closed two long arcs at once. The complexity arc that began in Chapter 14 — "how does cost grow with input?" — is complete: you can analyze loops and recursions, and you can prove a sorting algorithm optimal. And the Fibonacci arc that began in Chapter 6 is complete: defined recursively, proven about by induction, solved in closed form, and now computed in logarithmic time. The recurrence toolbox you have built — model it (Chapter 18), then solve it by tree, theorem, or substitution (this chapter) — is exactly what you will use to analyze every recursive algorithm in the rest of the book, from graph traversals to the divide-and-conquer routines hiding inside cryptographic and coding algorithms.

Part III now turns from counting and recursion to uncertainty. The next chapter introduces discrete probability: sample spaces, events, random variables, and expected value. The counting rules of Chapters 15–17 become the machinery for computing probabilities, and the same divide-and-think discipline you used on recurrences will help you reason about randomized algorithms — algorithms that flip coins to run fast on average. The squaring trick you just learned will even reappear, and the question "how long does this take on average?" will finally get a rigorous answer. That is Chapter 20.