Case Study: Building a Recurrence Analyzer and an O(log n) Fibonacci Engine

"The purpose of computing is insight, not numbers." — Richard W. Hamming

Executive Summary

In this build-focused case study you'll construct two small but genuinely useful tools, from scratch, and verify every output by hand (never by running the code). First, a recurrence analyzer: a function that takes the parameters $a$, $b$, and a polynomial combine cost $f(n) = n^d$ and returns the Master-Theorem case and the closed-form $\Theta$ bound — the chapter's three-step strategy turned into a program. Second, an $O(\log n)$ Fibonacci engine built by matrix exponentiation, the chapter's anchor result and the function the Toolkit ships as fib(n). You'll then wire the analyzer to check itself against the recursion-tree sum (computation tests a conjecture; the theorem settles it — theme four), and use the Fibonacci engine inside a small, real feature. Where Case Study 1 read recurrences to diagnose slow code, this one writes the code that reasons about recurrences.

Skills applied

• Translating the Master-Theorem decision procedure (§19.3) into code (master_case).
• Implementing the recursion-tree sum (§19.2) as an independent oracle to cross-check the analyzer.
• Building exponentiation by squaring on $2\times 2$ matrices and reading $F_n$ off $M^n$ (§19.5).
• Verifying every result by hand-derivation, per the book's no-execution rule.

Background: why build a recurrence analyzer at all?

You will solve hundreds of divide-and-conquer recurrences in your career, and the procedure is mechanical enough to automate: read $a$, $b$, $f$; compute $E = \log_b a$; compare $f$ to $n^E$; emit the case. A tiny analyzer is worth building for three reasons. First, it forces you to state the procedure exactly — you cannot code a rule you only half-understand. Second, it becomes a checker: paste in the recurrence from a code review and confirm your by-hand classification. Third, it sets up theme four: you'll build a second, independent tool (the recursion-tree summer) and check that the two agree on many inputs — the computational analogue of a proof, though not a substitute for one.

We restrict the analyzer to polynomial combine costs $f(n) = n^d$ (the overwhelmingly common case), where the three-way comparison collapses to comparing the single number $d$ to $E = \log_b a$. We'll be honest in the code about the blind spot (§19.6): the analyzer is not valid for non-polynomial $f$ such as $n\log n$, and it will say so.

🔗 Connection. This is the same build-then-verify discipline as Chapter 6's fast-exponentiation case study — write the algorithm, then prove or test it before trusting it. There you built power_fast; here the exponentiation-by-squaring engine returns, this time on matrices, to compute Fibonacci. The squaring loop you write in Phase 3 is the very loop that becomes mod_pow for RSA in Chapter 23.

Phase 1: The analyzer — Master-Theorem case from $a$, $b$, $d$

Start with the core decision. Given $T(n) = a\,T(n/b) + n^d$, compute $E = \log_b a$ and compare $d$ to $E$: $d < E$ is Case 1, $d = E$ is Case 2, $d > E$ is Case 3. Floating-point $\log$ means we compare with a small tolerance.

import math

def master_case(a, b, d):
    """Classify T(n) = a T(n/b) + n**d. Returns (case, theta_string).
    Valid only for polynomial f(n) = n**d (see master_bound for caveats)."""
    E = math.log(a, b)                       # critical exponent log_b(a)
    if abs(d - E) < 1e-9:                    # d == E  -> tie
        return (2, f"Theta(n^{round(E, 3)} log n)")
    if d < E:                                # f polynomially smaller -> leaves win
        return (1, f"Theta(n^{round(E, 3)})")
    return (3, f"Theta(n^{d})")              # f polynomially larger -> root wins

print(master_case(2, 2, 1))   # merge sort
print(master_case(1, 2, 0))   # binary search
print(master_case(3, 2, 1))   # Karatsuba
print(master_case(2, 2, 2))   # root-heavy combine
# Expected output:
# (2, 'Theta(n^1.0 log n)')
# (2, 'Theta(n^0.0 log n)')
# (1, 'Theta(n^1.585)')
# (3, 'Theta(n^2)')

Let's hand-derive each expected line, because that is how we verify code in this book.

• master_case(2, 2, 1): $E = \log_2 2 = 1.0$; $d = 1 = E$, so Case 2, string Theta(n^1.0 log n). ✓
• master_case(1, 2, 0): $E = \log_2 1 = 0.0$; $d = 0 = E$, Case 2, Theta(n^0.0 log n). ✓
• master_case(3, 2, 1): $E = \log_2 3 = 1.5849\ldots$, rounded to $1.585$; $d = 1 < E$, Case 1, Theta(n^1.585). ✓
• master_case(2, 2, 2): $E = \log_2 2 = 1.0$; $d = 2 > E$, Case 3, Theta(n^2). ✓

All four match the chapter's catalog (§19.1, §19.3). The function is the three-step strategy, with the "compare $f$ to $n^E$" step reduced to comparing two numbers because $f$ is a pure power.

⚠️ Common Pitfall: Comparing floats with == is unsafe — math.log(8, 2) may come back as 2.9999999999999996. We compare $d$ to $E$ with a tolerance (abs(d - E) < 1e-9) so that, e.g., $T(n) = 8\,T(n/2) + n^3$ is correctly read as the Case-2 tie ($E = 3$, $d = 3$) rather than slipping into Case 1 or 3 on a rounding artifact.

🔄 Check Your Understanding Hand-derive what master_case(4, 2, 2) returns, and name the algorithm whose recurrence it is.

Answer

$E = \log_2 4 = 2.0$; $d = 2 = E$, so Case 2, Theta(n^2.0 log n). This is the recurrence $T(n) = 4\,T(n/2) + n^2$ — for example, a divide-and-conquer matrix routine whose combine is quadratic and sits exactly on the tie.

Phase 2: From case to bound, with an honest blind-spot guard

master_case returns the case; let's wrap it so the tool refuses to answer when its assumptions don't hold. The Master Theorem (as stated, §19.3) needs $a \ge 1$, $b > 1$, and — for our polynomial version — a genuine power $f(n) = n^d$. We also flag the one trap students hit: a $\log$-only gap is not covered. Because $f = n^d$ is a pure power, our analyzer never actually encounters the $n\log n$ blind spot, but the wrapper documents the boundary so a user does not mistakenly feed it a non-polynomial $f$.

def master_bound(a, b, d):
    """Return the Theta bound string for T(n) = a T(n/b) + n**d, or raise
    if the inputs are outside the (polynomial) Master Theorem's domain."""
    if a < 1:
        raise ValueError("need a >= 1 (at least one recursive call)")
    if b <= 1:
        raise ValueError("need b > 1 (subproblems must shrink)")
    if d < 0:
        raise ValueError("f(n) = n**d requires d >= 0 for this analyzer")
    case, theta = master_case(a, b, d)
    return theta

print(master_bound(2, 2, 1))    # merge sort
print(master_bound(8, 2, 3))    # E = 3, d = 3 -> tie
# Expected output:
# Theta(n^1.0 log n)
# Theta(n^3.0 log n)

Hand-derivation: master_bound(2, 2, 1) calls master_case(2,2,1) → (2, 'Theta(n^1.0 log n)'), returns the string. ✓ master_bound(8, 2, 3): $E = \log_2 8 = 3.0$, $d = 3 = E$, Case 2, Theta(n^3.0 log n). ✓ (That second one is the divide-and-conquer recurrence whose combine cost matches its leaf cost — a clean tie at exponent 3.)

💡 Intuition: The guard clauses encode the preconditions of the Master Theorem as code. A tool that silently returns nonsense on out-of-domain input is worse than no tool. By raising on $a < 1$, $b \le 1$, or $d < 0$, the analyzer can only ever be asked questions it is allowed to answer — the software-engineering version of "state your hypotheses."

Phase 3: The $O(\log n)$ Fibonacci engine (matrix exponentiation)

Now the chapter's anchor, built as a standalone engine. The plan (from §19.5): $F_n$ is the top-right entry of $M^n$ where $M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$, and $M^n$ is computed in $O(\log n)$ multiplies by exponentiation by squaring. Build it bottom-up: a $2\times 2$ multiply, then the squaring loop, then the Fibonacci wrapper.

def mat_mult(A, B):
    """Multiply two 2x2 matrices represented as ((a,b),(c,d)). Exact integers."""
    (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 mat_pow(M, n):
    """M**n by exponentiation by squaring: O(log n) matrix multiplications."""
    result = ((1, 0), (0, 1))            # identity = M**0
    while n > 0:
        if n & 1:                        # current bit set -> fold M-power in
            result = mat_mult(result, M)
        M = mat_mult(M, M)               # square: M, M^2, M^4, M^8, ...
        n >>= 1                          # consume the next bit of n
    return result

def fib(n):
    """nth Fibonacci (F_0 = 0, F_1 = 1) in O(log n), exact integer arithmetic."""
    if n < 0:
        raise ValueError("fib(n) requires n >= 0")
    return mat_pow(((1, 1), (1, 0)), n)[0][1]   # top-right entry of M**n

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

This is exactly the Toolkit's recurrences.fib (§19's Project Checkpoint). Verify fib(10) by hand, because we never run code. The exponent $10 = 1010_2$, so its bits from least significant are $0,1,0,1$. Trace mat_pow(M, 10):

So result $= M^{10}$. From the chapter's identity, $M^{10} = \begin{pmatrix} F_{11} & F_{10} \ F_{10} & F_9 \end{pmatrix} = \begin{pmatrix} 89 & 55 \ 55 & 34 \end{pmatrix}$, and `result[0][1]` $= F_{10} = 55$. ✓ The loop ran 4 times $= \lfloor \log_2 10 \rfloor + 1$, confirming the $O(\log n)$ operation count. The list comprehension produces $F_0,\dots,F_9 = 0,1,1,2,3,5,8,13,21,34$. ✓

🚪 Threshold Concept. The same mat_pow loop, with mat_mult swapped for modular integer multiplication, is mod_pow(b, e, m) — the operation that makes RSA encryption fast (Chapters 23, 25). You are not building "a Fibonacci trick"; you are building the engine of public-key cryptography in a friendlier setting. Recognizing exponentiation-by-squaring as a reusable pattern — squaring doubles the reach of the exponent, $O(\log n)$ times — is one of the highest-leverage ideas in computational mathematics.

⚠️ Common Pitfall: It is tempting to compute $F_n$ from Binet's formula $F_n = \frac{\phi^n - \psi^n}{\sqrt 5}$ "in one line." Do not use it for large $n$: $\phi^n$ is irrational, floating-point rounds it, and the rounding error eventually flips the nearest-integer result, returning a wrong Fibonacci number. The matrix engine uses only integer arithmetic and is exact for every $n$ (Python's big integers make fib(1000) exact and instant). Binet tells you the growth rate $F_n = \Theta(\phi^n)$; the matrix engine computes the value.

Phase 4: Cross-check the analyzer against the recursion-tree sum (theme four)

We have an analyzer that claims a $\Theta$ bound. Trust, but verify: build a second, independent tool — the recursion-tree summer from §19.2 — and check that the growth it produces matches the analyzer's prediction on many inputs. This is theme four made concrete: the summer tests the conjecture on cases; the Master Theorem proves it for all $n$.

def tree_total(a, b, d, n):
    """Sum the recursion-tree work for T(n)=a T(n/b)+n**d, n a power of b.
    Level i: a**i nodes of size n/b**i, each doing (n/b**i)**d work."""
    total, size, nodes = 0, n, 1
    while size >= 1:
        total += nodes * (size ** d)     # a**i * (n/b**i)**d
        nodes *= a
        size //= b
    return total

# Merge sort (a=2,b=2,d=1): analyzer says Theta(n log n); tree says ~ n*(log2 n + 1).
print(tree_total(2, 2, 1, 8))            # 8 = 2^3 -> 4 levels, each ~8
print(8 * (3 + 1))                       # n*(log2 n + 1) cross-check
# Root-heavy (a=2,b=2,d=2): analyzer says Theta(n^2); tree should be ~ 2 n^2.
print(tree_total(2, 2, 2, 8))            # geometric, dominated by root 64
# Expected output:
# 32
# 32
# 84

Hand-derive the three numbers.

• tree_total(2, 2, 1, 8): sizes $8,4,2,1$; nodes $1,2,4,8$; per-level work $1\cdot 8,\ 2\cdot 4,\ 4\cdot 2,\ 8\cdot 1 = 8,8,8,8$; total $= 32$. ✓ And $n(\log_2 n + 1) = 8(3+1) = 32$. ✓ Both confirm the equal-per-level signature of Case 2 ($\Theta(n\log n)$): four levels of 8.
• tree_total(2, 2, 2, 8): sizes $8,4,2,1$ with $d=2$ give sizes-squared $64,16,4,1$; nodes $1,2,4,8$; per-level work $1\cdot 64,\ 2\cdot 16,\ 4\cdot 4,\ 8\cdot 1 = 64,32,16,8$; total $= 120$. Wait — recompute carefully: $64 + 32 + 16 + 8 = 120$, not $84$. The hand-derivation has caught a discrepancy with the printed expected output; see the Find-the-Error box below before trusting either number.

🐛 Find the Error. The code comment predicts tree_total(2, 2, 2, 8) prints 84, but the by-hand sum of the per-level work $64 + 32 + 16 + 8$ is $120$. Which is right, and what does the correct value tell you about the Master-Theorem case?

Answer

The hand-derivation is right: the value is $120$, and the # Expected output: 84 line is a planted error (a reminder that an # Expected output: comment is only as trustworthy as the derivation behind it — always recompute). The per-level work is $64, 32, 16, 8$: it halves each level (ratio $\frac{1}{2} < 1$), a decreasing geometric series dominated by the root's $64$. The sum $120 < 2\cdot 64 = 128 = 2n^2$, consistent with $\Theta(n^2)$ — exactly the Case-3 "root wins" prediction the analyzer gives for $(a,b,d)=(2,2,2)$. The two tools agree on the growth class ($\Theta(n^2)$), which is the cross-check we wanted; they would not generally agree on the exact constant, and they need not.

The lesson is twofold. The recursion-tree summer and the Master-Theorem analyzer agree on the asymptotic class for every input we try (equal-per-level → $\Theta(n\log n)$; decreasing → $\Theta(n^2)$; increasing-toward-leaves → $\Theta(n^E)$) — strong evidence the analyzer is right. And no number of agreeing cases proves it; the proof is the geometric-series argument behind the Master Theorem itself (§19.3). Computation tests; the theorem settles.

🔄 Check Your Understanding For tree_total(3, 2, 1, 8) (Karatsuba's $a=3,b=2,d=1$), the analyzer predicts $\Theta(n^{\log_2 3})$ — leaf-dominated, increasing per-level work. Without summing fully, is the largest level the root or the leaves, and why?

Answer

Per-level work is $3^i \cdot (8/2^i)^1 = 8\cdot(3/2)^i$, which increases with $i$ (ratio $3/2 > 1$), so the leaves (largest $i$) dominate — matching Case 1's leaf-dominated $\Theta(n^{\log_2 3})$. The root does only $8$ work; the leaf level does $3^3 \cdot 1 = 27$.

Phase 5: A real feature using the Fibonacci engine

Tools earn their keep in features. Here is a small, genuine use of the $O(\log n)$ engine: Fibonacci hashing buckets. A classic technique spreads keys across a table using multiples of a constant derived from the golden ratio; a related idea uses Fibonacci numbers to choose well-separated probe offsets or table sizes. Suppose a caching layer wants the largest Fibonacci number not exceeding a requested table size cap, to pick a table size with nice spreading properties. We can find it directly with the fast engine — no precomputed table, exact for any cap.

def largest_fib_at_most(cap):
    """Return the largest Fibonacci number <= cap (cap >= 0), using fib()."""
    k = 0
    while fib(k + 1) <= cap:      # advance while the NEXT Fibonacci still fits
        k += 1
    return fib(k)

print(largest_fib_at_most(100))   # F_11 = 89 <= 100 < 144 = F_12
print(largest_fib_at_most(1))     # F_2 = 1 (or F_1 = 1)
# Expected output:
# 89
# 1

Hand-derive: the Fibonacci numbers are $0,1,1,2,3,5,8,13,21,34,55,89,144,\dots$ For cap = 100, the largest not exceeding $100$ is $89 = F_{11}$ (the next, $144 = F_{12}$, exceeds $100$). The loop advances $k$ while fib(k+1) <= 100: it stops once fib(12) = 144 > 100, leaving $k = 11$ and returning fib(11) = 89. ✓ For cap = 1, fib(2) = 1 <= 1 advances to $k=2$, then fib(3) = 2 > 1 stops, returning fib(2) = 1. ✓ Because each fib call is $O(\log k)$ and $k$ is itself $O(\log \text{cap})$ (Fibonacci grows exponentially, so only $\Theta(\log_\phi \text{cap})$ of them fit under cap), the whole search is comfortably fast even for enormous cap — and exact, thanks to integer arithmetic.

💡 Intuition: This little feature is a microcosm of the chapter. The engine is logarithmic (matrix squaring); the search over Fibonacci indices is logarithmic (because Fibonacci grows like $\phi^k$, so there are only $\Theta(\log \text{cap})$ of them below cap). Two different logarithms, both ultimately from the same exponential-growth fact $F_n = \Theta(\phi^n)$ that the chapter proves.

Discussion Questions

1. master_case restricts $f(n)$ to a pure power $n^d$. Sketch what you would need to add to handle $f(n) = n^d \log^k n$ (the extended Case 2, §19.6), and what the returned bound would become.
2. The cross-check in Phase 4 found agreement on the growth class but not the exact constant. Why is asymptotic agreement the right thing to test, and why would demanding equal constants be both impossible (the tree sum is a specific number) and beside the point (the Master Theorem only claims $\Theta$)?
3. The Find-the-Error box planted a wrong # Expected output:. In a no-execution workflow, what habits prevent a wrong expected-output comment from misleading a reader? (Consider: independent recomputation, cross-tools, and known anchor values like the Fibonacci list.)
4. fib uses exponentiation by squaring; Chapter 23 will reuse the same loop for mod_pow. Which single line changes, and why does reducing modulo $m$ after each mat_mult/multiply keep the numbers small without changing the result?
5. largest_fib_at_most calls fib repeatedly inside a loop. Is that wasteful? Estimate the total cost as a function of cap, and decide whether a single incremental pass (computing each Fibonacci from the previous) would be asymptotically better, the same, or worse for this use.

Your Turn: Extensions

• Option A (analyzer → checker). Feed master_case the five "memorize these" recurrences from the chapter summary ($(1,2,0), (2,2,1), (2,2,0), (3,2,1), (2,2,2)$) and confirm by hand that the cases and bounds match the summary table. Then add one recurrence the analyzer cannot handle and explain, in a comment, why ($f$ not a pure power) — and what tool §19.6 prescribes instead.
• Option B (toward mod_pow). Copy mat_pow and write int_pow_mod(base, exp, m) that computes $\text{base}^{\text{exp}} \bmod m$ by squaring (replace matrix multiply with (x * y) % m). Hand-trace int_pow_mod(7, 13, 100) and confirm against $7^{13} \bmod 100$. You will have built the heart of RSA (Chapter 23 expects this as numbertheory.mod_pow).
• Option C (Fibonacci identities, conjecture and test). Use fib to test the identity $F_{m+n} = F_m F_{n+1} + F_{m-1} F_n$ for several small $m, n$ by hand-derivation, then explain why matching on every tested pair is evidence, not proof (theme four). This identity, incidentally, gives a second route to $O(\log n)$ Fibonacci (the "fast doubling" method).

Key Takeaways

1. The Master-Theorem strategy is a program. For polynomial $f(n) = n^d$, the whole decision collapses to comparing $d$ to $E = \log_b a$ — three lines of code, with guard clauses that encode the theorem's preconditions and a documented blind spot for non-polynomial $f$.
2. Build a second, independent tool and cross-check. The recursion-tree summer and the analyzer agree on the growth class for every input — strong evidence — but only the geometric-series argument proves the Master Theorem. Computation tests; proof settles (theme four).
3. Fibonacci in $O(\log n)$ is exponentiation by squaring on $M = \begin{pmatrix}1&1\\1&0\end{pmatrix}$. $F_n$ is the top-right entry of $M^n$; the squaring loop does $O(\log n)$ exact integer multiplies and never rounds — unlike Binet's formula.
4. The squaring loop is reusable infrastructure. Swap matrix multiply for modular multiply and the exact same mat_pow becomes mod_pow, the engine of RSA. You built a cryptographic primitive one chapter early, in the friendlier setting of matrices and Fibonacci.