The running time of a recursive algorithm is written as a recurrence: T(n) is expressed through T on smaller inputs plus the work of the call itself. This lesson shows three ways to solve it: unrolling/substitution, the recursion tree and the master theorem.
Four familiar recurrences
| Recurrence | Example | Solution |
|---|---|---|
T(n) = T(n-1) + c | factorial, list sum | O(n) |
T(n) = T(n-1) + n | recursive selection sort | O(n^2) |
T(n) = T(n/2) + c | binary search | O(log n) |
T(n) = 2T(n/2) + n | merge sort | O(n log n) |
T(n) = 2T(n-1) + c | two calls at every step | O(2^n) |
Unrolling: for T(n) = T(n-1) + n we get T(n) = n + (n-1) + (n-2) + ... + 1 = n(n+1)/2. The code below counts the real work of four recurrences, and the results match the theory.
def work_linear(n): # T(n) = T(n-1) + 1
return 0 if n == 0 else 1 + work_linear(n - 1)
def work_quad(n): # T(n) = T(n-1) + n
return 0 if n == 0 else n + work_quad(n - 1)
def work_log(n): # T(n) = T(n/2) + 1
return 0 if n <= 1 else 1 + work_log(n // 2)
def work_nlogn(n): # T(n) = 2T(n/2) + n
return 0 if n <= 1 else n + 2 * work_nlogn(n // 2)
for n in (16, 64, 256):
print(n, work_linear(n), work_quad(n), work_log(n), work_nlogn(n))16 16 136 4 64
64 64 2080 6 384
256 256 32896 8 2048