unrolling a linear recurrence
Not all recurrences come from balanced divide-and-conquer; many come from a single recursive call on a slightly smaller input, like T(n) = T(n-1) + something. The Master Theorem does not apply (it is built for T(n/b), not T(n-1)), but there is an even simpler tool: just expand the recurrence step by step until you see the pattern, then sum it up.
Unrolling (also called the iteration method) means repeatedly substituting the recurrence into itself. Take T(n) = T(n-1) + n. Substitute: T(n) = T(n-2) + (n-1) + n = T(n-3) + (n-2) + (n-1) + n, and continuing down to the base case T(0) = 0, we get T(n) = n + (n-1) + ... + 1 = sum from i=1 to n of i = n(n+1)/2 = Theta(n^2). The whole method is: unroll k times to spot the general term, push k all the way to the base case, and recognise the resulting sum (an arithmetic series, a geometric series, or a harmonic sum). T(n) = T(n-1) + 1 unrolls to a count of n steps, so Theta(n); T(n) = 2 T(n-1) + 1 unrolls to a geometric sum 1 + 2 + 4 + ... + 2^(n-1), so Theta(2^n).
Unrolling is the most transparent method when subproblem sizes decrease by subtraction rather than division — it shows up for recursion that peels off one element at a time, and for analysing simple loops. The honest caveat is to push the unrolling all the way to the base case and count the number of terms correctly: an off-by-one in how many times you can subtract before hitting the base changes a constant but, more dangerously, miscounting the series type (arithmetic vs geometric) changes the asymptotics entirely — n(n+1)/2 is Theta(n^2), but a geometric 2^n is exponentially worse.
T(n) = T(n-1) + c (constant work each step) unrolls to T(n) = T(0) + c*n = Theta(n) — a linear scan. But T(n) = 2 T(n-1) + 1 unrolls to 2^n - 1 = Theta(2^n) — naive recursive Fibonacci-style blow-up. Same 'minus one' shrink, wildly different totals because of the multiplier 2.
Expand the recurrence into a series, then sum it: arithmetic gives Theta(n^2), geometric can give Theta(2^n).
Identify the series correctly: a leading coefficient greater than 1 on the recursive term (like 2 T(n-1)) makes the sum geometric and the answer exponential, while coefficient 1 (T(n-1)) usually gives polynomial growth. Misreading this is the easiest way to be off by an exponential.