# The Master Theorem — Time & Space Complexity (Big-O)

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

> Solve divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n).

## A shortcut for divide and conquer

Many divide-and-conquer algorithms have recurrences of the form **T(n) = a·T(n/b) + f(n)**: the problem splits into **a** subproblems of size **n/b**, with **f(n)** work to divide and combine. The **master theorem** compares f(n) with the **critical function n^(log_b a)**, the total work done at the leaves of the recursion tree. **Case 1**: if f(n) grows **polynomially slower** than n^(log_b a), the leaves dominate and T(n) = **Θ(n^(log_b a))**. **Case 2**: if f(n) = Θ(n^(log_b a) · logᵏ n) for some k ≥ 0 (most often k = 0, the same rate), every level does about the same work and T(n) = **Θ(n^(log_b a) · logᵏ⁺¹ n)**. **Case 3**: if f(n) grows **polynomially faster** and satisfies a regularity condition (a·f(n/b) ≤ c·f(n) for some c < 1), the root dominates and T(n) = **Θ(f(n))**. The theorem does not apply to recurrences such as T(n) = T(n − 1) + n or to uneven splits, which need unrolling or the Akra–Bazzi method.

## Master theorem examples

Compute log_b a, compare with f(n), pick the case.

```text
recurrence                  a  b  n^(log_b a)    f(n)      case  result
--------------------------  -  -  -------------  --------  ----  --------------------
binary search: T(n/2)+1     1  2  n^0 = 1        1         2     Theta(log n)
merge sort: 2T(n/2)+n       2  2  n^1            n         2     Theta(n log n)
tree traversal: 2T(n/2)+1   2  2  n              1         1     Theta(n)
Karatsuba: 3T(n/2)+n        3  2  n^1.585        n         1     Theta(n^1.585)
Strassen: 7T(n/2)+n^2       7  2  n^2.807        n^2       1     Theta(n^2.807)
2T(n/2)+n^2                 2  2  n              n^2       3     Theta(n^2)

not applicable: T(n) = T(n-1) + n   (subtract, not divide) -> unroll: Theta(n^2)
```

## Compute log_b a first

Most mistakes come from comparing f(n) with the wrong exponent. Write down a, b and log_b a explicitly, then compare f(n) with n^(log_b a) before choosing a case.

**Quiz:** Using the master theorem, what is T(n) = 4T(n/2) + n?

- [x] Θ(n²)
- [ ] Θ(n)
- [ ] Θ(n log n)
- [ ] Θ(n² log n)

*Answer:* Θ(n²). log₂ 4 = 2, so n^(log_b a) = n², which dominates f(n) = n: case 1 gives Θ(n²).