Recurrence analysis

A recurrence expresses the cost of an input of size n in terms of smaller inputs. Read it off the code: the number of recursive calls gives a, how much the size shrinks gives b (or the subtraction), and the work outside the calls gives f(n).

Examples: binary search T(n) = T(n/2) + O(1). Merge sort T(n) = 2T(n/2) + O(n). Factorial T(n) = T(n - 1) + O(1). Naive Fibonacci T(n) = T(n - 1) + T(n - 2) + O(1). Tower of Hanoi T(n) = 2T(n - 1) + O(1).

The number of calls is the number of nodes in the recursion tree. With branching factor a and depth h the tree has up to a^h leaves. For the linear recursion factorial it is n + 1 nodes; for naive fib(n) about 1.6^n; for Hanoi 2^n - 1.

Counting nodes is often the fastest way to find the time when the work per call is constant. Run the Fibonacci animation with n = 5, 6, 7, 8 and compare the node counts to φⁿ.

The stack depth is the longest chain of pending calls, which is the height of the recursion tree, not its size. Naive Fibonacci makes an exponential number of calls but is only n deep, so it uses O(n) stack. Merge sort is log₂ n deep. Recursive quick sort is n deep in the worst case.

Depth matters for StackOverflowError and for the space complexity of the algorithm (the stack counts as memory).

For T(n) = a·T(n/b) + Θ(n^d) with a ≥ 1, b > 1 and d ≥ 0, compare d with the critical exponent log_b a. Case 1: if d < log_b a, then T(n) = Θ(n^(log_b a)); the leaves dominate. Case 2: if d = log_b a, then T(n) = Θ(n^d log n); every level costs the same. Case 3: if d > log_b a, then T(n) = Θ(n^d); the root dominates.

Use the calculator: drag a, b and d, or use the presets. The table shows the work per level of the tree. Whichever case you are in, the shape of that column tells you why: growing, flat or shrinking.

Spending memory can save time. Memoization stores answers to subproblems so each is computed once: naive Fibonacci uses O(n) stack and O(φⁿ) time, the memoized version uses O(n) stack plus an O(n) table and O(n) time.

The reverse also happens: recomputing instead of storing saves memory. Choose by looking at both the recurrence and the stack depth. A bottom-up loop (lesson 5.07) gets the time benefit with O(1) stack.