Exercises: Solving Recurrence Relations

These build from mechanical warm-ups — reading $a$, $b$, $f$ off a recurrence — to full recursion-tree derivations, Master-Theorem classifications, code, modeling, and proof. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md; do them before you peek.

Unless a problem says otherwise, every recurrence has a constant base case $T(n) = \Theta(1)$ for $n$ below some threshold, and you may drop floors and ceilings (§19.1). When a problem says "$n$ a power of $b$," assume it so the tree is perfectly balanced.

Part A — Warm-ups: read off $a$, $b$, $f$, and classify (⭐)

19.1 † For each recurrence, identify $a$, $b$, and $f(n)$, then compute the critical exponent $E = \log_b a$. (a) $T(n) = 2\,T(n/2) + n$ (b) $T(n) = 9\,T(n/3) + n^2$ (c) $T(n) = T(n/4) + 1$ (d) $T(n) = 7\,T(n/2) + n^2$ (e) $T(n) = 4\,T(n/2) + n^3$.

19.2 A recursive function makes five recursive calls, each on one-fifth of the input, and does $\Theta(n)$ work to split and combine. Write its divide-and-conquer recurrence and state $a$, $b$, $f(n)$.

19.3 † For $T(n) = 8\,T(n/2) + n^2$, compute $n^E = n^{\log_b a}$ as an explicit power of $n$. Is $f(n) = n^2$ polynomially smaller than, equal to, or polynomially larger than $n^E$?

19.4 Match each recurrence to its $\Theta$ solution from the chapter's catalog (§19.1, §19.3): no derivation needed, just recall. (a) $T(n) = T(n/2) + \Theta(1)$ (b) $T(n) = 2\,T(n/2) + \Theta(n)$ (c) $T(n) = 2\,T(n/2) + \Theta(1)$ (d) $T(n) = 3\,T(n/2) + \Theta(n)$. Choices: $\Theta(n)$, $\Theta(\log n)$, $\Theta(n \log n)$, $\Theta(n^{\log_2 3})$.

19.5 † True or false, with one sentence each: (a) In $T(n) = a\,T(n/b) + f(n)$, the number $a$ counts the pieces the input is cut into. (b) The recursion tree for $T(n) = a\,T(n/b) + f(n)$ has height $\log_b n$. (c) The number of leaves of that tree is $n^{\log_b a}$.

19.6 Read off the recurrence from this code skeleton (do not solve it yet — just write $T(n) = a\,T(n/b) + f(n)$ and identify $a$, $b$, $f$):

def solve(arr):           # n = len(arr)
    if len(arr) <= 1:
        return base(arr)               # O(1)
    third = len(arr) // 3
    x = solve(arr[:third])             # recurse on one third
    y = solve(arr[third:2*third])      # recurse on the next third
    return combine(x, y, arr)          # Theta(n) combine

19.7 For each, state whether the Master Theorem could apply at all (is it of the form $a\,T(n/b) + f(n)$ with constants $a\ge 1$, $b>1$?). Answer yes/no with a one-phrase reason — do not solve: (a) $T(n) = 2\,T(n/2) + n$; (b) $T(n) = T(n-1) + 1$; (c) $T(n) = \sqrt{n}\,T(\sqrt n) + n$; (d) $T(n) = 4\,T(n/2) + n^2$.

Part B — Ordinary computation: solve by the Master Theorem (⭐⭐)

For each, give $E = \log_b a$, name the case (1, 2, or 3), and state $T(n)$. For any Case 3, show the regularity check $a\,f(n/b) \le c\,f(n)$ explicitly.

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

19.9 † $T(n) = 4\,T(n/2) + n^2$.

19.10 $T(n) = 4\,T(n/2) + n^3$.

19.11 † $T(n) = 2\,T(n/4) + \sqrt{n}$. (Recall $\sqrt n = n^{1/2}$.)

19.12 $T(n) = 16\,T(n/4) + n^2$.

19.13 † $T(n) = 3\,T(n/3) + n$. (Where have you seen this shape before?)

19.14 $T(n) = 7\,T(n/2) + n^2$. (This is Strassen's matrix-multiplication recurrence — compare its exponent to the naive $\Theta(n^3)$.)

19.15 † $T(n) = 2\,T(n/2) + \dfrac{n}{2}$. (Careful: a constant factor on $f$ does not change its $\Theta$ class — which case is this?)

19.16 A student writes "$T(n) = 2\,T(n/2) + n^2$ is Case 1 because $f(n) = n^2$ and $n^2$ is big." Without redoing their work, state the correct case and the correct answer, and name in one phrase what they got backwards.

Part C — Prove it (with scaffolding) (⭐⭐)

19.17 † (Scaffolded recursion-tree sum.) Solve $T(n) = 3\,T(n/2) + n$ by the recursion-tree method (assume $n$ is a power of $2$). Fill in the blanks. - At level $i$ there are $\underline{\hphantom{xxxx}}$ nodes, each of size $n/2^i$, each doing $n/2^i$ work, so the work at level $i$ is $\underline{\hphantom{xxxx}} \cdot \dfrac{n}{2^i} = n \cdot \underline{\hphantom{xxxx}}$. - The per-level work is a geometric series with ratio $r = \underline{\hphantom{xxxx}}$. Because $r > 1$, the sum is dominated by its $\underline{\hphantom{xxxx}}$ term (the leaves). - The number of leaves is $3^{\log_2 n} = n^{\underline{\hphantom{xxxx}}}$, so $T(n) = \Theta\!\left(n^{\underline{\hphantom{xxxx}}}\right)$. - Confirm with the Master Theorem: $E = \log_2 3$, $f(n) = n$, so this is Case $\underline{\hphantom{xx}}$, giving the same answer.

19.18 (Scaffolded matrix induction.) Complete the inductive step of the proof that $M^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}$ for $M = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}$. Assume $M^k = \begin{pmatrix} F_{k+1} & F_k \ F_k & F_{k-1} \end{pmatrix}$. Then $M^{k+1} = M^k \cdot M = \underline{\hphantom{xxxxxxxxxxxx}}$ (multiply the matrices). Using the Fibonacci recurrence $F_{j+1} = F_j + F_{j-1}$, the top-left entry $F_{k+1} + F_k$ simplifies to $\underline{\hphantom{xxxx}}$ and the bottom-left $F_k + F_{k-1}$ to $\underline{\hphantom{xxxx}}$, so the product equals $\underline{\hphantom{xxxxxxxxxxxx}}$, which is $M^{k+1}$ in the desired form.

19.19 † (Substitution method.) The recurrence $T(n) = 2\,T(n/2) + n$ has solution $\Theta(n\log n)$. Prove the upper bound $T(n) \le c\,n \log_2 n$ for all $n \ge 2$ by induction (substitution), for a suitable constant $c$. Use $T(1) = 1$, treat $T(n) = 2\,T(n/2) + n$ as exact, and assume $n$ is a power of $2$. Outline to fill in: state the inductive hypothesis for $n/2$; substitute it into the recurrence; simplify $2 \cdot c (n/2)\log_2(n/2) + n$; show it is $\le c\,n\log_2 n$ when $c \ge 1$.

19.20 (Substitution, lower bound.) For the same recurrence, prove the matching lower bound $T(n) \ge c'\,n\log_2 n$ for some constant $c' > 0$. Together with 19.19 this establishes $T(n) = \Theta(n\log n)$ without invoking the Master Theorem.

19.21 † (Scaffolded — exponentiation by squaring is logarithmic.) The cost of computing $M^n$ by squaring satisfies $T(n) = T(n/2) + \Theta(1)$ (each step halves the exponent at $\Theta(1)$ cost). Fill in: this is the same recurrence as $\underline{\hphantom{xxxxxx}}$ (name the algorithm); by the Master Theorem $E = \log_2 1 = \underline{\hphantom{xx}}$, $f(n) = \Theta(1) = \Theta(n^{\underline{\hphantom{xx}}})$, so it is Case $\underline{\hphantom{xx}}$, giving $T(n) = \Theta(\underline{\hphantom{xxxx}})$.

Part D — Find the error (⭐⭐)

Each argument below is flawed. State precisely which step fails and why; give the correct conclusion.

19.22 Claim: $T(n) = 2\,T(n/2) + n\log n$ solves to $\Theta(n\log n)$ by Master-Theorem Case 2. "Reasoning": "$E = \log_2 2 = 1$, and $f(n) = n\log n = \Theta(n^1)$, so it's a tie, Case 2, giving $\Theta(n^1 \log n) = \Theta(n\log n)$." — Find the flaw and give the correct answer.

19.23 † Claim: the naive Fibonacci $T(n) = T(n-1) + T(n-2) + \Theta(1)$ is $\Theta(n)$. "Reasoning": "It's a divide-and-conquer recurrence with two subproblems and constant extra work, like merge sort but with $b = 1$, so by the Master Theorem with $a = 2$, $E = \log_1 2$ — well, that's undefined, so just call it linear." — Identify every thing wrong here and give the correct growth rate.

19.24 Claim: $T(n) = 2\,T(n/2) + n^3$ is Case 3, so $T(n) = \Theta(n^3)$ — and the student writes "Case 3 holds because $n^3$ is bigger than $n$, done." Their answer is correct, but their justification omits a required step. Name it, then carry it out to show the answer really does stand.

19.25 † Claim: "Binary search and merge sort both cut the array in half, so they have the same recurrence and therefore the same running time." Diagnose the error in the recurrence, write both recurrences correctly, and give both running times.

19.26 Claim: "Computing $F_n$ with Binet's formula $F_n = \frac{\phi^n - \psi^n}{\sqrt 5}$ is $O(1)$ and exact, so it beats the $O(\log n)$ matrix method." One word of this is defensible and one is wrong. Say which, and explain why the matrix method is preferred for computing exact values at large $n$.

Part E — Implement it (⭐⭐)

Write Python for each. Do not run it — hand-trace and include an # Expected output: comment, matching the book's convention. Reference solutions are in code/exercise-solutions.py.

19.27 † Write a function master_case(a, b, d) that classifies $T(n) = a\,T(n/b) + n^d$ (a polynomial $f(n) = n^d$) by comparing $d$ to $E = \log_b a$: return 1, 2, or 3. Trace it on $(a,b,d) = (2,2,1)$ (merge sort), $(1,2,0)$ (binary search), and $(2,2,2)$ (root-heavy). (You may use math.log; remember to compare with a tolerance, not ==.)

19.28 Write a function tree_levels(a, b, f, n) that returns the list of per-level work $[a^0 f(n), a^1 f(n/b), \dots]$ for a recursion tree, stopping when the subproblem size drops below 1 (use integer division for the size). Trace it for merge sort's $a=2, b=2, f(n)=n$ on $n = 8$ and report the list and its sum.

19.29 † Write an iterative fib_fast(n) using exponentiation by squaring on the matrix $M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$, returning $F_n$ (the top-right entry of $M^n$), with $F_0 = 0$. Trace fib_fast(10) and [fib_fast(k) for k in range(8)]. (This is the Toolkit's fib; keep it exact — integer arithmetic only.)

19.30 Write fib_naive(n) and, separately, a fib_memo(n) that caches results in a dictionary. You do not need to time them; instead, add a one-line comment to each stating its asymptotic running time ($\Theta(\phi^n)$ vs. $\Theta(n)$) and why. Trace fib_memo(10).

19.31 † Write tree_total(a, b, d, n) that sums the recursion-tree work for $T(n) = a\,T(n/b) + n^d$ on $n$ a power of $b$ (one number, not a list). Trace it on $(a,b,d,n) = (2,2,1,8)$ and confirm it equals $n(\log_2 n + 1) = 32$. Then trace $(2,2,2,8)$ and report the sum (recompute by hand — don't trust a guessed comment).

Part F — Model it & Conjecture and test (⭐⭐⭐)

19.32 † (Model it.) A media-streaming service stores its catalog of $n$ titles in a sorted index and answers "is title $X$ in the catalog?" by binary search; on a miss it then queries a slower backup store in $\Theta(n)$ time. Model the worst-case cost of a single lookup as a function of $n$ (combine the search and the possible fallback), and give its $\Theta$ class. Then model a redesign that sorts a batch of $m$ incoming titles with merge sort before doing $m$ binary-search lookups; write the total cost as a function of $m$ and $n$ and identify which term dominates when $m \ll n$.

19.33 (Model it.) You are choosing between two multiplication algorithms for $n$-digit integers: grade-school multiplication at $\Theta(n^2)$, and Karatsuba at $T(n) = 3\,T(n/2) + \Theta(n)$. (a) Solve Karatsuba's recurrence. (b) For roughly what input size does the asymptotically faster one start to win, qualitatively — and why does the answer involve the constant factors the $\Theta$ hides? (c) Suppose a rival "improves" Karatsuba to use only $2$ subproblems: $T(n) = 2\,T(n/2) + \Theta(n)$. What does that recurrence solve to, and would it beat grade-school multiplication asymptotically?

19.34 † (Conjecture and test, then prove.) Define $G(n) = T(n)/n$ where $T(n) = 2\,T(n/2) + n$ with $T(1) = 1$, for $n$ a power of $2$. Compute $G(n)$ for $n = 1, 2, 4, 8, 16$ (by hand or with the code from 19.31, summing levels), conjecture a closed form for $G(n)$ in terms of $\log_2 n$, then prove your conjecture by substitution/induction. What does $G(n)$ being unbounded tell you about whether merge sort is linear?

19.35 (Conjecture and test, then prove or disprove.) A classmate conjectures: "For any constants $a \ge 1, b > 1$, the recurrence $T(n) = a\,T(n/b) + n$ is $\Theta(n\log n)$." Use the Master Theorem to test the conjecture on at least three different $(a,b)$ pairs — including $(a,b) = (2,2)$, $(a,b) = (4,2)$, and $(a,b) = (2,4)$ — then either prove the conjecture or give a precise corrected statement (for which $(a,b)$ is it $\Theta(n\log n)$, and what is it otherwise?).

19.36 (Conjecture and test, Fibonacci.) It is a classical identity that $\gcd(F_m, F_n) = F_{\gcd(m,n)}$. Using the Toolkit's `fib` (the $O(\log n)$ version from this chapter) and Python's math.gcd, write three lines that test this identity for all pairs $(m,n)$ with $1 \le m, n \le 12$. State what output would confirm it on every tested pair, and explain (theme four) why passing the test is evidence, not a proof.

19.37 † (Conjecture and test, the doubling ratio.) For a routine with running time $T(n) = \Theta(n^d)$, the *doubling ratio* $T(2n)/T(n)$ tends to the constant $2^d$. (a) Compute the predicted doubling ratio for $d = 1$ (linear), $d = 2$ (quadratic), and $d = \log_2 3$ (Karatsuba). (b) For $T(n) = \Theta(n\log n)$, show the doubling ratio is not a constant but tends to $2$ from above, and write its exact form $\frac{T(2n)}{T(n)}$ assuming $T(n) = n\log_2 n$. (c) Explain how this gives a cheap empirical test for "is my routine quadratic or linearithmic?" — connect to theme four.

Part G — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

19.38 (Ch. 18 + 19.) Classify each recurrence as linear / subtractive (Chapter 18's characteristic-equation territory) or divide-and-conquer (this chapter's Master-Theorem territory), and name the tool you'd use: (a) $a_n = 3a_{n-1} - 2a_{n-2}$; (b) $T(n) = 2\,T(n/2) + n$; (c) $T(n) = T(n-1) + \Theta(n)$; (d) $T(n) = 7\,T(n/2) + n^2$.

19.39 † (Ch. 14 + 19.) Order these growth classes from slowest to fastest, then label which sorting or searching algorithm from the chapter each one is: $\Theta(n^2)$, $\Theta(\log n)$, $\Theta(n\log n)$, $\Theta(n)$, $\Theta(n^{\log_2 3})$.

19.40 (Ch. 11 + 19.) The recursion-tree method reduces a recurrence to a geometric series. For $T(n) = 2\,T(n/2) + n^2$, write the exact finite geometric sum $\sum_{i=0}^{\log_2 n} (\text{per-level work})$, evaluate it using the finite geometric-series formula $\sum_{i=0}^{k} r^i = \frac{r^{k+1}-1}{r-1}$ (Ch. 11), and confirm the leading term is $\Theta(n^2)$.

19.41 † (Ch. 6 + 19.) The substitution method is induction (Chapter 6). For the recurrence $T(n) = T(n/2) + 1$ with $T(1) = 1$ ($n$ a power of $2$), guess $T(n) = \log_2 n + 1$ and prove it by induction. State $P(n)$, the base case, and the inductive step explicitly.

19.42 (Ch. 18 + 19.) The naive Fibonacci's running time satisfies $T(n) = T(n-1) + T(n-2) + \Theta(1)$. Using Chapter 18's characteristic equation, explain why $T(n) = \Theta(\phi^n)$ where $\phi = \frac{1+\sqrt5}{2}$, and connect this to why the naive recursion is exponential while the matrix method is logarithmic.

19.43 † (Ch. 14 + 18 + 19, Deep Dive.) Prove the leaf-count identity $a^{\log_b n} = n^{\log_b a}$ used throughout §19.2, starting from the definition of logarithms. (Hint: take $\log_b$ of both sides, or write $a = b^{\log_b a}$ and substitute.) Then explain in one sentence why this single identity is what makes $n^{\log_b a}$ — not $a^{\log_b n}$ — the quantity that appears in the Master Theorem.

19.44 (Deep Dive — prove the Master Theorem, Case 1.) Specialize the recursion-tree sum $T(n) = \sum_{i=0}^{\log_b n} a^i f(n/b^i)$ to $f(n) = n^c$ with $c < E = \log_b a$. Show the per-level work increases geometrically toward the leaves, so the sum is $\Theta$ of its last term, the leaf work $n^{\log_b a}$. (You have just proved Case 1 from first principles.)

19.45 † (Deep Dive — prove the Master Theorem, Case 2.) Specialize the recursion-tree sum to $f(n) = n^E$ with $E = \log_b a$. Show every term equals $n^E$, count the terms, and conclude $T(n) = \Theta(n^E \log n)$. (You have just proved Case 2 from first principles.)

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each classification, the rubric rewards: the correct $a$, $b$, $f(n)$; the correct $E = \log_b a$; the right case with a stated reason ("polynomially smaller/equal/larger"); the regularity check whenever Case 3 is claimed; and a clean $\Theta$ answer.