The Master Theorem — Senior Level¶

The Master Theorem is rarely the hard part of a real analysis — the hard part is recognizing when your recurrence does not fit its mold, choosing the right generalization (Akra–Bazzi, the extended form, or raw substitution), and not handing an interviewer or a design doc a confidently-wrong Θ bound because you skipped the regularity check or ignored unequal subproblem sizes.

Table of Contents¶

1. Introduction
2. Reading Recurrences Off Real Algorithms
3. The Failure Modes: When the Master Theorem Lies
4. Akra–Bazzi for Messy Recurrences
5. Automated Recurrence Analysis
6. Interview and Design-Review Pitfalls
7. Code Examples
8. Empirical Verification of Asymptotics
9. Asymptotics vs. Real Runtime: Constants and Crossovers
10. Parallel Divide-and-Conquer: Work, Span, and the Master Theorem
11. Case Studies in Algorithm Design
12. Decision Framework
13. Summary

1. Introduction¶

At the senior level you stop asking "what does the Master Theorem say" and start deciding "does the Master Theorem even apply, and if not, what is the cheapest rigorous path to a tight bound." Three things distinguish a senior analysis:

1. Recurrence extraction is the bottleneck. Getting a, b, f(n) right from a real algorithm — including the cost of the split and combine steps, which are easy to undercount — matters more than the lookup that follows.
2. The Master Theorem has sharp edges. Unequal subproblem sizes, non-polynomial f, failing regularity, and variable b all produce recurrences where a naive application gives a wrong answer, not just no answer.
3. Generalizations are the senior's toolkit. Akra–Bazzi subsumes the Master Theorem and handles Σ a_i T(n/b_i) + f(n) with different b_i, plus floors, ceilings, and small perturbations. Knowing it turns "the Master Theorem doesn't apply" from a dead end into a one-integral computation.

This document is about judgment: extracting recurrences correctly, spotting the failure modes, and reaching for Akra–Bazzi or substitution when the Master Theorem bows out.

2. Reading Recurrences Off Real Algorithms¶

The single most common senior mistake is miscounting f(n). The recurrence is T(n) = a·T(n/b) + f(n) where f(n) is all the non-recursive work: the cost to split the input and the cost to combine the results.

Pitfall: undercounting the combine. Engineers often write T(n) = 2T(n/2) + O(1) for merge sort because the split is O(1), forgetting the O(n) merge. That mistake turns a Case 2 (n log n) into a Case 1 (Θ(n)) — off by a log n factor. Always account for the combine.

Pitfall: hidden work in the split. Quicksort's split is the O(n) partition; the combine is free. The recurrence is still 2T(n/2) + Θ(n), but the cost lives in a different phase. The Master Theorem doesn't care which phase — it only sees f(n) — but you must count both phases.

Pitfall: data-dependent a or b. Quicksort with a bad pivot degrades to T(n−1) + Θ(n) = Θ(n²) — a subtract-and-conquer recurrence, outside the Master Theorem entirely. The "balanced" recurrence only holds in expectation or with median-of-medians pivoting.

3. The Failure Modes: When the Master Theorem Lies¶

The Master Theorem applies only when all of these hold:

1. a ≥ 1 constant, b > 1 constant.
2. Exactly one subproblem size n/b (all a subproblems equal).
3. f(n) asymptotically positive.
4. For Cases 1/3, the gap to the watershed is polynomial (n^ε).
5. For Case 3, the regularity condition holds.

Violate any one and the theorem is silent or wrong. The four failure modes a senior must recognize on sight:

3.1 Unequal subproblem sizes¶

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

There is no single b. The Master Theorem cannot start. (Akra–Bazzi gives Θ(n log n).) Spotting this is reflexive: two different fractions of n inside T(...) ⇒ not the Master Theorem.

3.2 Non-polynomial gap (the log-factor trap)¶

T(n) = 2T(n/2) + n log n        →  f bigger than n by only log → Case 3 FAILS
T(n) = 2T(n/2) + n / log n      →  f smaller than n by only log → Case 1 FAILS

The first is rescued by the extended Case 2 (Θ(n log² n)); the second is not (negative k), and needs Akra–Bazzi (Θ(n log log n)). A naive engineer "rounds" n log n up to n^1.0001 and declares Case 3 — wrong.

3.3 Regularity failure¶

Pathological f like f(n) = n²·(2 + sin n) is Ω(n²) and looks like Case 3 for T(n)=2T(n/2)+f(n), but a·f(n/b) ≤ c·f(n) fails because the oscillation breaks the smoothness. The Master Theorem gives no conclusion; you fall back to bounding by hand.

3.4 Non-constant a or b¶

T(n) = √n · T(√n) + n

Here both the branching factor and the shrink factor depend on n. The Master Theorem is inapplicable; this is a "tree of square roots" that solves to Θ(n log log n) by a change of variable m = log n.

4. Akra–Bazzi for Messy Recurrences¶

The Akra–Bazzi theorem generalizes the Master Theorem to:

T(n) = Σ_{i=1}^{k} a_i · T(n / b_i  + h_i(n))  +  g(n)

with a_i > 0, b_i > 1 constants, |h_i(n)| = O(n / log² n) (small perturbations, absorbing floors/ceilings), and g(n) polynomially bounded with bounded derivative growth. Define the Akra–Bazzi exponent p as the unique real solving:

Σ_{i=1}^{k}  a_i / b_i^p  =  1

Then:

T(n) = Θ( n^p · ( 1 + ∫_1^n  g(u) / u^(p+1)  du ) )

The exponent p is the critical exponent — for the single-term Master case a/b^p = 1 gives p = log_b a, recovering the watershed exactly. The integral plays the role of the geometric series.

4.1 Worked: T(n) = T(n/3) + T(2n/3) + n¶

Solve Σ a_i/b_i^p = 1: with b_1 = 3, b_2 = 3/2, both a_i = 1:

(1/3)^p + (2/3)^p = 1   →   p = 1   (since 1/3 + 2/3 = 1)

Then T(n) = Θ(n^1 (1 + ∫_1^n u/u² du)) = Θ(n (1 + ln n)) = Θ(n log n). ✓

4.2 Worked: Median-of-medians T(n) = T(n/5) + T(7n/10) + n¶

(1/5)^p + (7/10)^p = 1

At p = 1: 0.2 + 0.7 = 0.9 < 1, so we need p < 1 to raise the sum; but at p = 0: 1 + 1 = 2 > 1. The unique solution is some p < 1. Since p < 1, the integral term dominates: ∫_1^n u/u^(p+1) du = ∫ u^(−p) du = Θ(n^(1−p)), so T(n) = Θ(n^p · n^(1−p)) = Θ(n). The selection algorithm is linear. ✓ (The key is 1/5 + 7/10 = 9/10 < 1: the subproblems shrink in total, forcing p < 1, forcing linear.)

4.3 Worked: T(n) = 2T(n/2) + n/log n¶

Single term, a/b^p = 2/2^p = 1 ⇒ p = 1. Integral: ∫_1^n (u/log u)/u² du = ∫ 1/(u log u) du = ln ln n. So T(n) = Θ(n (1 + ln ln n)) = Θ(n log log n). ✓ — exactly the case the Master Theorem could not touch.

Akra–Bazzi is the senior's universal solvent: whenever the Master Theorem stalls on unequal sizes, floors/ceilings, or log-factor gaps, the integral closes the problem.

5. Automated Recurrence Analysis¶

In tooling (compilers estimating complexity, static analyzers, teaching systems) you sometimes want a program to classify recurrences. The pipeline:

1. Parse the recurrence into (a, b, c, k) for f(n) = n^c log^k n, or into a list of (a_i, b_i) plus g for Akra–Bazzi.
2. Master-Theorem fast path. If single-term and f is n^c log^k n, classify by comparing c to log_b a (with the extended-case logic for the tie).
3. Akra–Bazzi fallback. Otherwise, numerically root-find p from Σ a_i/b_i^p = 1 (monotone in p — bisection converges fast), then numerically evaluate the integral ∫_1^n g(u)/u^(p+1) du to determine whether it dominates n^p or not.
4. Report the tightest Θ bound found, or "no closed form" if g is not admissible.

The robustness concern is floating-point comparison of c to log_b a: log_2 3 is irrational, so the equality test for Case 2 needs an epsilon, and a true tie (like log_2 4 = 2 exactly) must be detected symbolically when possible. Senior tooling keeps a, b as exact rationals and compares b^c against a exactly to avoid misclassifying a borderline recurrence.

6. Interview and Design-Review Pitfalls¶

A senior gives the case number, the regularity check (if Case 3), and the watershed — not just the final Θ. In a design review, that traceability is what lets a teammate catch a misread f(n) before it becomes a perf bug.

6.1 A template for documenting a complexity claim¶

When you assert a bound in a design doc or PR, make it auditable:

Algorithm: parallel merge sort
Recurrence (work):  T1(n) = 2·T1(n/2) + Θ(n)      [split O(1), merge O(n)]
  a=2, b=2, f=Θ(n), watershed = n^(log_2 2) = n
  f = Θ(watershed) → Case 2 → T1(n) = Θ(n log n)
Recurrence (span):  T∞(n) = T∞(n/2) + Θ(n)        [serial merge]
  a=1, b=2, f=Θ(n), watershed = n^0 = 1
  f = Ω(n^(0+1)), regularity 1·(n/2)=½f ✓ → Case 3 → T∞(n) = Θ(n)
Parallelism: T1/T∞ = Θ(log n)
Validated: log-log slope fit over n∈[2^16, 2^22] gives 1.04 ≈ 1 (×log) ✓

Every line is checkable. A reviewer who suspects the merge is actually O(n log n) (because someone sorts inside it) can re-derive Case-2-with-k and catch the discrepancy. This discipline — recurrence, watershed, case, regularity, validation — is the difference between a complexity claim that survives review and one that becomes a 2 a.m. incident.

6.2 The "it depends on the input" caveat¶

Many real recurrences only hold in expectation or with high probability. Randomized quicksort's 2T(n/2)+Θ(n) is an expected recurrence; the worst case is T(n−1)+Θ(n) = Θ(n²). A senior states which model the bound assumes: "expected Θ(n log n) over random pivots; worst case Θ(n²); median-of-medians pivoting makes it worst-case Θ(n log n) at a constant-factor cost." Quoting the expected bound as if it were worst-case is a classic senior-interview red flag.

7. Code Examples¶

Example: Unified Solver — Master Theorem with Akra–Bazzi Fallback¶

Go¶

package main

import (
    "fmt"
    "math"
)

// akraBazziExponent solves sum_i a_i / b_i^p = 1 by bisection.
func akraBazziExponent(a, b []float64) float64 {
    f := func(p float64) float64 {
        s := 0.0
        for i := range a {
            s += a[i] / math.Pow(b[i], p)
        }
        return s - 1.0
    }
    lo, hi := -5.0, 50.0 // f is monotone decreasing in p
    for it := 0; it < 200; it++ {
        mid := (lo + hi) / 2
        if f(mid) > 0 {
            lo = mid
        } else {
            hi = mid
        }
    }
    return (lo + hi) / 2
}

// solveSingle uses the Master Theorem for one subproblem size; falls back to p.
func solveSingle(a, b, c float64) string {
    crit := math.Log(a) / math.Log(b)
    const eps = 1e-9
    switch {
    case c < crit-eps:
        return fmt.Sprintf("Case 1: Theta(n^%.4f)", crit)
    case math.Abs(c-crit) <= eps:
        return fmt.Sprintf("Case 2: Theta(n^%.4f log n)", crit)
    default:
        return fmt.Sprintf("Case 3: Theta(n^%.4f)", c)
    }
}

func main() {
    fmt.Println("merge sort:", solveSingle(2, 2, 1))
    // median-of-medians: T(n/5)+T(7n/10)+n, g(n)=n grows faster than n^p (p<1)
    p := akraBazziExponent([]float64{1, 1}, []float64{5, 10.0 / 7.0})
    fmt.Printf("median-of-medians p=%.4f -> g=n dominates -> Theta(n)\n", p)
    // T(n/3)+T(2n/3)+n
    p2 := akraBazziExponent([]float64{1, 1}, []float64{3, 1.5})
    fmt.Printf("T(n/3)+T(2n/3)+n p=%.4f -> Theta(n log n)\n", p2)
}

Java¶

public class UnifiedSolver {

    static double akraBazziExponent(double[] a, double[] b) {
        java.util.function.DoubleUnaryOperator f = p -> {
            double s = 0;
            for (int i = 0; i < a.length; i++) s += a[i] / Math.pow(b[i], p);
            return s - 1.0;
        };
        double lo = -5.0, hi = 50.0;
        for (int it = 0; it < 200; it++) {
            double mid = (lo + hi) / 2;
            if (f.applyAsDouble(mid) > 0) lo = mid; else hi = mid;
        }
        return (lo + hi) / 2;
    }

    static String solveSingle(double a, double b, double c) {
        double crit = Math.log(a) / Math.log(b);
        final double eps = 1e-9;
        if (c < crit - eps) return String.format("Case 1: Theta(n^%.4f)", crit);
        if (Math.abs(c - crit) <= eps) return String.format("Case 2: Theta(n^%.4f log n)", crit);
        return String.format("Case 3: Theta(n^%.4f)", c);
    }

    public static void main(String[] args) {
        System.out.println("merge sort: " + solveSingle(2, 2, 1));
        double p = akraBazziExponent(new double[]{1, 1}, new double[]{5, 10.0 / 7.0});
        System.out.printf("median-of-medians p=%.4f -> Theta(n)%n", p);
        double p2 = akraBazziExponent(new double[]{1, 1}, new double[]{3, 1.5});
        System.out.printf("T(n/3)+T(2n/3)+n p=%.4f -> Theta(n log n)%n", p2);
    }
}

Python¶

import math


def akra_bazzi_exponent(a, b):
    """Solve sum_i a_i / b_i^p = 1 by bisection (f monotone decreasing in p)."""
    def f(p):
        return sum(ai / (bi ** p) for ai, bi in zip(a, b)) - 1.0
    lo, hi = -5.0, 50.0
    for _ in range(200):
        mid = (lo + hi) / 2
        if f(mid) > 0:
            lo = mid
        else:
            hi = mid
    return (lo + hi) / 2


def solve_single(a, b, c):
    crit = math.log(a) / math.log(b)
    eps = 1e-9
    if c < crit - eps:
        return f"Case 1: Theta(n^{crit:.4f})"
    if abs(c - crit) <= eps:
        return f"Case 2: Theta(n^{crit:.4f} log n)"
    return f"Case 3: Theta(n^{c:.4f})"


if __name__ == "__main__":
    print("merge sort:", solve_single(2, 2, 1))
    p = akra_bazzi_exponent([1, 1], [5, 10 / 7])
    print(f"median-of-medians p={p:.4f} -> Theta(n)")
    p2 = akra_bazzi_exponent([1, 1], [3, 1.5])
    print(f"T(n/3)+T(2n/3)+n p={p2:.4f} -> Theta(n log n)")

What it does: classifies single-size recurrences with the Master Theorem and falls back to root-finding the Akra–Bazzi exponent p for unequal sizes. Run: go run main.go | javac UnifiedSolver.java && java UnifiedSolver | python solver.py

8. Empirical Verification of Asymptotics¶

When you suspect a misclassification, measure. Instrument the algorithm to count its basic operations as a function of n, then fit a curve.

import math


def op_count(recur_fn, sizes):
    return [(n, recur_fn(n)) for n in sizes]


def merge_sort_ops(n):
    """Exact comparisons-ish count: T(n)=2T(n/2)+n, T(1)=0."""
    if n <= 1:
        return 0
    return 2 * merge_sort_ops(n // 2) + n


sizes = [2 ** k for k in range(4, 16)]
for n, ops in op_count(merge_sort_ops, sizes):
    ratio = ops / (n * math.log2(n))   # should approach a constant -> Theta(n log n)
    print(f"n={n:6d}  ops={ops:9d}  ops/(n log n)={ratio:.3f}")

If ops / (n log n) converges to a constant, you have empirical evidence for Case 2. Divide by the wrong closed form (say n²) and the ratio drifts toward 0 — a quick way to falsify a misapplied Case 3. This doubling-and-fitting technique is how seniors sanity-check a theoretical bound against reality before trusting it in a perf budget.

8.1 The log-log slope method¶

A more robust empirical test: plot log(runtime) against log(n). For a pure-power T(n) = Θ(n^α), the points fall on a line of slope α. Fit the slope by least squares over the largest sizes (where lower-order terms have faded):

import math


def estimate_exponent(sizes, times):
    """Least-squares slope of log(time) vs log(n) -> estimated exponent alpha."""
    xs = [math.log(n) for n in sizes]
    ys = [math.log(t) for t in times]
    m = len(xs)
    mx, my = sum(xs) / m, sum(ys) / m
    num = sum((x - mx) * (y - my) for x, y in zip(xs, ys))
    den = sum((x - mx) ** 2 for x in xs)
    return num / den


# Example: synthetic n^2.807 (Strassen) data
sizes = [2 ** k for k in range(6, 13)]
times = [n ** 2.807 for n in sizes]
print(f"estimated alpha = {estimate_exponent(sizes, times):.3f}")  # ~2.807

A measured slope near log_2 7 ≈ 2.807 confirms a Strassen-style recurrence; a slope near 3.0 says you accidentally fell back to naive multiply (perhaps below the crossover). For Case-2 algorithms the slope is log_b a with a slow log correction, so the fit drifts slightly upward as n grows — itself a fingerprint of the log factor. This slope method is the senior's first move when a production perf regression looks "super-linear but I'm not sure how super."

8.2 Guarding against silent complexity regressions¶

In a long-lived service, an innocent refactor can turn a Θ(n) combine into a Θ(n log n) one (e.g. someone adds a sort inside the merge), bumping a Case-2 algorithm to extended Case 2 and inflating latency by a log n factor. Guard with a CI benchmark that asserts the fitted exponent stays within a band: fail the build if the measured slope exceeds, say, 1.1 × log_b a. This catches the regression before it reaches production, where it would manifest as creeping tail latency under growing load.

9. Asymptotics vs. Real Runtime: Constants and Crossovers¶

The Master Theorem describes the limit. Production engineering lives in the regime where constants and crossovers dominate, and a senior is expected to bridge the two.

9.1 The Strassen crossover¶

Strassen's Θ(n^2.807) beats naive Θ(n^3) asymptotically, but Strassen does 18 matrix additions per level versus naive's fewer, plus extra memory traffic. The crossover where Strassen actually wins is typically n ≈ 500–1000 depending on cache and the recursion-base cutoff. Below the cutoff, libraries (e.g. tuned BLAS) fall back to blocked naive multiply. The recurrence the library obeys is therefore a hybrid:

T(n) = 7 T(n/2) + Θ(n²)   for n > cutoff
T(n) = Θ(n³)              for n ≤ cutoff (blocked naive, but constant-bounded)

The Master Theorem still gives Θ(n^2.807) because the cutoff is a constant; but the constant factor hidden in Θ is what the cutoff tunes.

9.2 The base-case cutoff in sorts¶

Real merge sort and quicksort switch to insertion sort below n ≈ 16–32. This does not change the Θ(n log n), but it removes the recursion overhead for the Θ(n / cutoff) small subproblems — a measurable constant-factor win. The recurrence's asymptotic class is robust to this; the wall-clock time is not.

9.3 When a worse asymptotic wins in practice¶

The senior lesson: the Master Theorem tells you which algorithm wins eventually, and the crossover — found empirically — tells you when "eventually" begins. Both numbers belong in a design doc.

10. Parallel Divide-and-Conquer: Work, Span, and the Master Theorem¶

Divide-and-conquer parallelizes naturally: the a subproblems are independent. Two quantities matter, and each is a Master-Theorem recurrence.

• Work T₁(n) — total operations, as if run serially. This is the ordinary recurrence a·T(n/b) + f(n).
• Span T∞(n) — the critical-path length, assuming infinite processors. Since the a subproblems run in parallel, the recursive term is a single T∞(n/b) (not a of them), plus the parallel depth of the combine, f∞(n):

T∞(n) = T∞(n/b) + f∞(n).

Example — parallel merge sort with serial merge. Work T₁(n) = 2T₁(n/2) + n = Θ(n log n). Span T∞(n) = T∞(n/2) + n (serial merge has depth n) → Case 3 → Θ(n). Parallelism = work/span = Θ(log n) — poor.

Example — parallel merge sort with parallel merge. If the merge itself is parallelized to depth Θ(log² n), the span recurrence becomes T∞(n) = T∞(n/2) + log² n → watershed n^0 = 1, Case... f = log² n vs watershed 1: this is a gap (polylog over constant), giving T∞(n) = Θ(log³ n). Parallelism jumps to Θ(n log n / log³ n) = Θ(n / log² n) — vastly better.

The Master Theorem (and its extended/Akra–Bazzi forms for the gap cases) is the tool for both the work and span analyses. A senior designing a parallel algorithm computes both recurrences and reports the parallelism T₁/T∞.

11. Case Studies in Algorithm Design¶

11.1 Closest pair of points (2D)¶

Sort by x, split in half, recurse, then a Θ(n) strip merge: T(n) = 2T(n/2) + Θ(n) → Case 2 → Θ(n log n). The senior insight is that the Θ(n) strip merge is non-obvious — naively the strip could be Θ(n²), but the geometric packing argument bounds each point's comparisons by a constant, keeping f(n) = Θ(n) and the algorithm linearithmic. Mis-analyzing the combine as Θ(n²) would (falsely) push it to Case 3 and Θ(n²).

11.2 Integer multiplication ladder¶

• Schoolbook: Θ(n²).
• Karatsuba 3T(n/2)+n → Θ(n^1.585) (Case 1).
• Toom-Cook-3 5T(n/3)+n → log_3 5 ≈ 1.465 (Case 1) → Θ(n^1.465).
• Toom-Cook-k (2k−1)T(n/k)+n → log_k(2k−1) → 1 as k → ∞.
• FFT-based (Schönhage–Strassen) → Θ(n log n log log n), beyond the Master Theorem.

Each rung lowers log_b a by raising b faster than a, exactly the leaf-floor lever from professional.md Section 14. The Master Theorem makes the whole ladder legible at a glance.

11.3 Matrix multiplication ladder¶

naive 8T(n/2)+n² → n³; Strassen 7T(n/2)+n² → n^2.807; later algorithms (Coppersmith–Winograd and successors) push the exponent toward the theoretical ω (currently ≈ 2.37), but those are not simple aT(n/b) recurrences — they use rectangular tensor techniques outside the Master Theorem. Knowing where the Master Theorem stops (at Strassen-style square recurrences) is itself senior knowledge.

12. Decision Framework¶

1. Is it T(n) = a·T(n/b) + f(n), single size, a,b constant?
   NO  → unequal sizes / variable a,b  → Akra–Bazzi (or change of variable)
   YES → continue
2. Is f(n) = n^c log^k n (polynomial × polylog)?
   NO  → substitution / recursion tree by hand
   YES → continue
3. Compare c to log_b a:
   c < log_b a          → Case 1 → Θ(n^log_b a)
   c = log_b a, k ≥ 0   → extended Case 2 → Θ(n^log_b a · log^(k+1) n)
   c = log_b a, k < 0   → gap → Akra–Bazzi
   c > log_b a          → check regularity a·f(n/b) ≤ c·f(n):
                            holds → Case 3 → Θ(f(n))
                            fails → bound by hand

This framework is the senior deliverable: not just an answer, but a traceable path from recurrence to bound that a reviewer can audit.

12.1 A checklist for production complexity claims¶

[ ] Recurrence written with split AND combine cost accounted for
[ ] a, b confirmed constant and a >= 1, b > 1
[ ] Single subproblem size? (else -> Akra-Bazzi)
[ ] f(n) polynomial or polynomial*polylog? (else -> substitution)
[ ] Watershed n^(log_b a) computed explicitly
[ ] Case identified (1 / 2 / ext-2 / 3)
[ ] If Case 3: regularity a*f(n/b) <= c*f(n), c<1 verified
[ ] Model stated: worst-case / expected / amortized / high-probability
[ ] Empirically validated: log-log slope fit within band of log_b a
[ ] Crossover noted if a constant-factor-heavy algorithm (Strassen, FFT)

Running this checklist turns "I think it's n log n" into a defensible engineering statement. The two lines that catch the most real bugs are the combine cost line (forgetting the merge) and the model line (quoting expected as worst-case).

12.2 Quick triage table for an unknown recurrence¶

Most production recurrences fall in the first three rows; recognizing the bottom four as out of scope is what prevents a confidently-wrong bound.

13. Summary¶

Senior-level mastery of the Master Theorem is mostly about its boundaries. Extracting a, b, f(n) correctly from real algorithms — counting both the split and combine work — is where most errors originate, and a miscounted combine silently shifts merge sort from Case 2 to Case 1. The theorem genuinely fails on unequal subproblem sizes, non-polynomial (log-factor) gaps, regularity violations, and non-constant a/b; recognizing these on sight is the senior skill. The universal fallback is Akra–Bazzi, whose exponent p (solving Σ a_i/b_i^p = 1) generalizes the watershed and whose integral generalizes the geometric series — it dispatches median-of-medians (Θ(n)), T(n/3)+T(2n/3)+n (Θ(n log n)), and 2T(n/2)+n/log n (Θ(n log log n)) in one framework. In interviews and design reviews, deliver the case number, the regularity check, and the watershed — a traceable derivation, not just a Θ. And when in doubt, instrument and measure: the ratio ops / (predicted closed form) converging to a constant is the cheapest proof that your classification is right.