Setting Up Recurrence Relations

A recurrence relation for an algorithm's running time is an equation that defines $T(n)$, the worst-case (or sometimes average-case) number of primitive operations on an input of size $n$, in terms of $T$ evaluated at smaller arguments. It comes in two parts. The base case specifies $T(n)$ directly for small, fixed values of $n$ — typically the input sizes at which the algorithm stops recursing and does $O(1)$ work. The recursive case specifies $T(n)$ for larger $n$ as a combination of calls to $T$ at smaller arguments, plus whatever extra work the algorithm performs outside those calls. The most common shape, arising from divide-and-conquer algorithms, is

read as: the algorithm divides a problem of size $n$ into $a$ subproblems, each of size roughly $n/b$, solves each recursively, and then spends $f(n)$ time combining the subproblem results (this $f(n)$ also absorbs the cost of dividing the input in the first place). Here $a \geq 1$ is the number of recursive calls, $b > 1$ is the factor by which the input shrinks, and $f(n)$ is called the combine cost or driver function. Not every recursive algorithm fits this exact template — some have unequal subproblem sizes (e.g., quicksort's worst case), some subtract rather than divide (e.g., $T(n) = T(n-1) + O(n)$), and some make a variable number of calls depending on the input — but the discipline of identifying "how many calls, how much smaller, how much extra work" applies universally. The key terminology to keep straight: subproblem size is the argument passed to each recursive call, not the number of calls; branching factor ($a$) is how many separate recursive invocations occur, not how many times the function shrinks the problem; and combine cost ($f(n)$) is measured per call at size $n$, using the same operation-counting techniques used for iterative loops. Confusing any of these three produces a recurrence that looks plausible but describes a different algorithm than the one in front of you.

Setting up a recurrence is a mechanical, five-step reading of the code — you are not yet solving anything, only transcribing.

Step 1 — Identify the parameter of recursion. Decide what "$n$" measures: array length, tree height, number of bits, distance between two indices, and so on. This must be a quantity that strictly decreases toward the base case along every recursive path.

Step 2 — Find every base case and its cost. Locate each `if`/guard that stops the recursion (e.g., `n <= 1`, `lo >= hi`, `node == null`). Count the operations performed there exactly as you would for straight-line code. This gives $T(n) = \Theta(1)$ (or whatever constant work applies) for those small $n$.

Step 3 — Count the recursive calls and their argument sizes. For each call to the function itself, note the size of the argument passed. If there are $a$ calls each on a problem of size $n/b$, that contributes $a \cdot T(n/b)$. If sizes are unequal (say sizes $n_1, \dots, n_k$), write $\sum_i T(n_i)$ instead of forcing them into a single $T(n/b)$ term — do not paper over asymmetry.

Step 4 — Count everything else as $f(n)$. Sum the cost of every operation that is not a recursive call: splitting/partitioning the input, scanning it, merging results, allocating auxiliary arrays, comparisons used to decide how to recurse. Use ordinary loop-counting to get $f(n)$ as an explicit function of $n$ (e.g., $\Theta(n)$ for a linear merge, $\Theta(1)$ for computing a midpoint).

Step 5 — Assemble and simplify. Write

and simplify $f(n)$ to its tightest simple bound (e.g., write $\Theta(n)$ rather than "$n-1$ comparisons plus 2 assignments"). At this point $T(n)$ is fully specified; solving it is a separate task handled by later techniques. ``` FUNCTION SetUpRecurrence(code): // Step 1: identify the recursion parameter n n := the quantity that shrinks on every recursive path // Step 2: locate base case(s) for each stopping condition in code: record cost of that branch as a constant // T(n) = Θ(1) there // Step 3: locate recursive calls calls := list of (argument size, count) for each self-call if all calls have the same size n/b and there are a of them: recursive_term := a * T(n / b) else: recursive_term := sum of T(size_i) over each distinct call // Step 4: count non-recursive work f_n := cost of everything in code EXCLUDING the recursive calls (splitting, scanning, merging, bookkeeping) // analyze this exactly as an iterative loop would be analyzed // Step 5: assemble T(n) := base_case_cost if n small T(n) := recursive_term + f_n otherwise return T(n) ``` To see this in action, consider merge sort on an array of length $n$: ``` MERGE-SORT(A, lo, hi): if lo >= hi: // base case: 0 or 1 element return mid = (lo + hi) / 2 MERGE-SORT(A, lo, mid) // recursive call #1, size ~n/2 MERGE-SORT(A, mid+1, hi) // recursive call #2, size ~n/2 MERGE(A, lo, mid, hi) // combine step, Θ(n) work ``` Applying the five steps: the recursion parameter is $n = hi - lo + 1$; the base case is $n \le 1$ costing $\Theta(1)$; there are $a = 2$ recursive calls each on roughly $n/2$ elements, so $b = 2$; the non-recursive work is the `MERGE` call, which scans and merges two sorted halves in $\Theta(n)$ time. Assembling gives

This is the recurrence that The Master Theorem later solves to $\Theta(n \log n)$ — but notice that arriving at $2T(n/2) + \Theta(n)$ required nothing beyond careful reading; no solving happened yet.

Setting up the recurrence is not itself an algorithm with a running time — it is an act of modeling. So "complexity" here means: how do we know the recurrence we wrote is a faithful and tight description of the algorithm's actual cost? Correctness of the setup rests on three checks, each corresponding to a place errors creep in.

Check 1 — base case fidelity. The base case in $T(n)$ must trigger for exactly the same inputs as the base case in the code, and its stated cost must match the actual work done there (not assumed to be free). If code checks `n <= 1` but the recurrence assumes `n == 0`, sizes like $n=1$ get silently routed through the recursive branch of $T$, which may not even be defined for such a small argument (e.g., $n/2$ under integer division could loop or misbehave). This is why Correctness of Recursive Algorithms by Induction and recurrence setup are companions: the induction proof of correctness and the recurrence for cost must use identical base cases, since both rely on the same well-founded decrease in $n$.

Check 2 — recursive term fidelity. The number of calls $a$ and the subproblem size $n/b$ must be read directly from the call sites, not guessed from the algorithm's name or reputation. A common trap is writing $T(n/2)$ when the code actually recurses on sizes $n/2$ and $n/2 - 1$ (fine, both are $\Theta(n)$-close and usually absorbed), versus code that recurses on wildly unequal pieces, such as quicksort's worst case ($0$ and $n-1$), which must be written as $T(0) + T(n-1)$, not forced into a balanced template.

Check 3 — combine-cost completeness. $f(n)$ must include all non-recursive work: splitting the array, computing a pivot, allocating temporary storage, and any post-processing after the recursive calls return — not just the step that "feels" like the combine phase. Undercounting here is the single most common source of an incorrect asymptotic bound; for instance, forgetting that array slicing (rather than passing indices) costs $\Theta(n)$ per call silently upgrades a $\Theta(n\log n)$ recurrence to $\Theta(n^2)$ in practice, because $f(n)$ was mis-recorded as $\Theta(1)$. Given these checks, the recurrence is a correct model in the following precise sense: if $T_{\text{code}}(n)$ denotes the true number of primitive steps the algorithm performs on an input of size $n$, and $T(n)$ is the recurrence built by the five-step procedure, then $T_{\text{code}}(n) = T(n)$ exactly (up to the constants hidden in $\Theta$-notation for the base case and $f(n)$), by structural induction on $n$: the base case matches by Check 1, and for the inductive step, the code's total work at size $n$ is by definition the sum of the work done in the recursive calls — which by the inductive hypothesis is $\sum_i T_{\text{code}}(n_i) = \sum_i T(n_i)$ — plus the non-recursive work $f(n)$ by Check 3, which is exactly the recursive case of $T(n)$. The honest tradeoff is that this setup step produces $T(n)$ but does not tell you its closed form or growth rate; that is deferred to The Substitution Method, The Recursion-Tree Method, and The Master Theorem. A perfectly set-up recurrence can still be hard to solve (e.g., $T(n) = T(n-1) + T(n-2) + O(1)$, the Fibonacci recurrence, grows exponentially despite looking similar in shape to easier ones), so setup and solving are genuinely separate skills, and mistakes in either stage compound.

Consider a recursive algorithm for finding the maximum of an array by splitting it into three (not two) unequal parts, a variant deliberately chosen to avoid the too-clean symmetric case: ``` MAX3(A, lo, hi): n = hi - lo + 1 if n == 1: return A[lo] if n == 2: return max(A[lo], A[hi]) third = n / 3 m1 = lo + third m2 = lo + 2third x = MAX3(A, lo, m1) // size ~ n/3 y = MAX3(A, m1+1, m2) // size ~ n/3 z = MAX3(A, m2+1, hi) // size ~ n/3 (or n - 2(n/3), possibly larger by rounding) return max(x, max(y, z)) // Θ(1) combine ``` Walk through the five steps explicitly.

A subtlety worth pausing on: the three subproblem sizes are not identical (integer division makes the last chunk possibly one or two elements larger), but since they differ by at most $O(1)$, it is standard and justified practice to write $3T(n/3)$ rather than $T(\lceil n/3\rceil) + T(\lceil n/3 \rceil) + T(n - 2\lceil n/3\rceil)$ — the discrepancy only affects lower-order terms, which the solving techniques (The Master Theorem in particular) are explicitly built to absorb. This is a judgment call that setup requires: know when rounding is safe to elide (bounded, $O(1)$-additive discrepancies) versus when it changes the asymptotics (as with unbalanced splits like $1/4$ vs. $3/4$, which still needs the shape $a\,T(n/b)$ but with different constants per branch if sizes are genuinely proportionally unequal). Now trace the recurrence numerically for $n = 9$ to double check it against direct code execution, assuming $f(n) = 1$ unit exactly and $T(1) = T(2) = 1$ unit:

Cross-checking against the code: at $n=9$, three recursive calls each on size 3 (so 9 total leaf-level base cases at $n=1$, each costing 1, giving $9$ units), plus the internal combine steps at each of the 4 internal invocation levels shown above (the top call plus 3 middle calls = 4 combine steps of 1 unit each) gives $9 + 4 = 13$ — matching exactly. This numeric cross-check is a good habit: after setting up $T(n)$, unroll it two or three levels by hand and compare against a direct trace of the code on a small concrete input, as a sanity check before handing the recurrence off to a solving method.

The systematic use of recurrence relations to analyze algorithms emerged alongside the formalization of divide-and-conquer as a design paradigm, though the mathematics of recurrences long predates computing.

Recurrence setup is the analytical backbone behind every divide-and-conquer library routine in practice: standard sorting implementations (merge sort variants used in Python's Timsort, Java's `Arrays.sort` for objects, and C++'s `std::stable_sort`) are all designed and tuned by first writing down and solving their recurrences, then choosing thresholds (like switching to insertion sort below some small $n$) informed by the base-case behavior of $T(n)$. Fast multiplication algorithms — Karatsuba's algorithm and the Fast Fourier Transform-based methods used in cryptographic libraries and big-integer arithmetic (as in Python's `int`, or GMP) — are justified by recurrences like $T(n) = 3T(n/2) + \Theta(n)$, whose solved form directly explains why they beat naive $\Theta(n^2)$ multiplication. Computational geometry algorithms (closest-pair, convex hull) and recursive tree/graph algorithms (binary search tree operations, recursive descent parsers used in every compiler front-end) are all analyzed the same way. In distributed and parallel computing, recurrences of the form $T(n) = T(n/2) + O(\log n)$ describe communication rounds in parallel algorithms, guiding real infrastructure decisions such as how MapReduce-style reduction trees or parallel prefix-sum implementations are structured. Anywhere a system recurses — compilers, database query planners choosing between recursive join strategies, or recursive descent in regular-expression engines — setting up the recurrence correctly is the first analytical step engineers take before trusting a recursive implementation at scale.

Ask the tutor: How do I set up the recurrence for an algorithm that recurses a variable number of times depending on the input, rather than a fixed count like 2 or 3?