# Writing Recurrence Relations — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/r-recurrences

> Express the running time of recursive functions as recurrences and solve simple ones.

## Time defined in terms of itself

A recursive algorithm's running time is naturally described by a **recurrence**: T(n) expressed using T on smaller inputs plus the work done at the current level. **Factorial** or summing a list recursively makes one call on n − 1 and does constant work: **T(n) = T(n − 1) + O(1)**, which unrolls to **O(n)**. **Binary search** makes one call on half the input: **T(n) = T(n/2) + O(1)**, giving **O(log n)**. **Merge sort** makes two calls on halves and merges in linear time: **T(n) = 2T(n/2) + O(n)**, giving **O(n log n)**. A function that makes two calls on n − 1, such as naive Fibonacci, gives **T(n) = T(n − 1) + T(n − 2) + O(1)**, which grows **exponentially**. Solve simple recurrences by **unrolling** (substituting repeatedly until a pattern appears), by a **recursion tree**, by the **master theorem** for divide-and-conquer forms, or by guessing and proving with **induction** (the substitution method).

## Unrolling a recurrence

Each substitution exposes one more level until the base case is reached.

![A vertical chain of boxes shrinking in width step by step, each labelled only with a small arrow, ending at a tiny base box.](assets/figures/big-o/section-4-map.svg) — Figure 4.1 — Expanding T(n) step by step down to the base case.

## Recurrences for three classic functions

The recurrence follows directly from the number and size of the recursive calls.

```python
def total(a, i=0):
    if i == len(a):
        return 0
    return a[i] + total(a, i + 1)
# T(n) = T(n-1) + O(1)  ->  O(n)

def bsearch(a, t, lo, hi):
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if a[mid] == t:
        return mid
    return bsearch(a, t, mid + 1, hi) if a[mid] < t else bsearch(a, t, lo, mid - 1)
# T(n) = T(n/2) + O(1)  ->  O(log n)

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    return merge(left, right)        # O(n) merge
# T(n) = 2T(n/2) + O(n)  ->  O(n log n)

# unrolling T(n) = T(n-1) + c:
# T(n) = T(n-2) + 2c = T(n-3) + 3c = ... = T(0) + n*c  ->  O(n)
```

## Slicing has a cost

In Python, `a[:mid]` copies elements, costing O(n) time and memory per call. Merge sort pays that anyway in its merge step, but a binary search written with slices becomes O(n) instead of O(log n). Pass indices instead.

**Quiz:** Which recurrence describes binary search?

- [ ] T(n) = 2T(n/2) + O(n)
- [ ] T(n) = T(n − 1) + O(n)
- [x] T(n) = T(n/2) + O(1)
- [ ] T(n) = 2T(n − 1) + O(1)

*Answer:* T(n) = T(n/2) + O(1). Binary search does constant work and recurses on one half of the input.