Recipe

Derive and solve a recursive algorithm's running-time recurrence

Use when: you're given a recursive algorithm's code or description and asked how its running time grows with the input size n

Goal: a running-time recurrence T(n), solved directly or matched to a growth rate already known

Taught in Recursion in algorithms

1. 1

   Identify every recursive call the algorithm makes in one invocation, and the smaller input size each call runs on.

   Example

   Consider an algorithm that solves a problem of size n by calling itself twice, each time on a problem of size n-1.

   Why: the running-time recurrence's shape comes directly from exactly which smaller calls the code makes, nothing else.

2. 2

   Add one T term for each call found in the previous step, evaluated at its own smaller size, plus a term for the work done outside those calls.

   Example

   With two calls on n-1 and one unit of outside work, T(n)=2T(n-1)+1, with base case T(0)=0.

   • exactly one recursive call — a single T(n-k) term, plus the outside work.
   • two or more recursive calls — one T(n-k) term per call, all added together, plus the outside work.

   Why: the total work at size n is exactly the work done outside the calls plus whatever each smaller call itself costs.

3. 3

   If the recurrence unwinds directly, solve it by iteration; if its shape matches a recurrence already solved earlier in this course, its growth rate is already known.

   Example

   Unwinding T(n)=2T(n-1)+1 from T(0)=0 gives T(1)=1, T(2)=3, T(3)=7, T(4)=15, matching the pattern T(n)=2^n-1.

   • the calls all shrink by the same fixed amount — unwind directly and look for the pattern, the way Section 6 does.
   • the recurrence's shape matches one already solved elsewhere, such as the Fibonacci recurrence — its growth rate is already known without unwinding again.

   Why: re-deriving a growth rate from scratch wastes effort once the recurrence's shape matches one this course already solved.

4. 4

   Report what the solved recurrence says about how much work the algorithm does, keeping that separate from whatever number the algorithm actually returns.

   Example

   This algorithm's running time T(n)=2^n-1 grows exponentially, even though the value it eventually returns could be something else entirely.

   Why: a running-time recurrence counts steps taken, and a value-computing recurrence counts a returned number, so matching shapes doesn't make them the same quantity.