The Master Theorem

Divide-and-conquer algorithm

A typical divide-and-conquer algorithm solves a problem of size $n$ as follows:

Divide: Break the problem into $a$ problems of size at most $n/b$ and solve them recursively. We assume that $a ≥ 1$ and $b > 1$.

Conquer: Combine the answers found by recursive calls to an answer for the initial problem.

Therefore, the algorithm makes $a$ recursive calls to problems of size $n/b$.

Note: $b$ does not necessarily divide $n$, so instead of $n/b$, we should usually write $⌈n/b⌉$. Still, we write $n/b$; it simplifies the notation and does not break the analysis.

Assume that everything that is done outside of recursive calls takes time $O(n^d)$ where $d$ is a non-negative constant. This includes preparing the recursive calls and combining the results.

Since this is a recursive algorithm, we also need to specify conditions under which a problem is solved directly rather than recursively (with no such base case, a recursion would never stop). This usually happens when $n$ becomes small. For simplicity, we assume that it is $n = 1$ and that the running time of the algorithm is equal to $1$ in this case.

Therefore, by denoting the running time of the algorithm on problems of size $n$ by $T (n)$, we get the following recurrence relation on $T(n)$:

$$T(n) = \begin{cases} 1 & \text{if }~~ n = 1, \\ aT(\frac{n}{b})+O(n^d) & \text{if }~~ n > 1. \end{cases}$$

Below, we show that we can find out the growth rate of $T (n)$ by looking at parameters $a$, $b$, and $d$. Before doing this, we illustrate how this recurrence relation captures some well-known algorithms.

Binary search

To search for a key in a sorted sequence of length $n$, the binary search algorithm makes a single recursive call for a problem of size $n/2$. Outside this recursive call, it spends time $O(1)$. Therefore, $a = 1,b = 2,d = 0$. Therefore,

$$T(n) = T(\frac{n}{2})+O(1).$$

The running time of the binary search algorithm is $O(log n)$ since there are at most $log_2 n$ recursive calls. Another way to see this is to unwind the recurrence relation as shown below, that is, to apply the same equality to $T (n/2)$, $T (n/4)$, and so on:

$$\begin{aligned}{} T (n) &= T (n/2) + c = \\ &= T (n/4) + 2c = \\ &= T (n/8) + 3c = \\ & \space \space \space \vdots \\ &= T (n/2^k) + kc = \\ & \space \space \space \vdots \\ &= T (1) + log_2 n \cdot c = O(log n)\\ \end{aligned}$$

Here, $c$ is a constant from the $O(1)$ term.

Merge sort

To sort an array of length $n$, the $MergeSort$ algorithm breaks it into two subarrays of size $n/2$, sorts them recursively, and merges the results. The time spent by the algorithm before and after two recursive calls is $O(n)$. Therefore, $a = 2, b = 2, d = 1$. Therefore,

$$T(n)=2T(\frac{n}{2}) +O(n).$$

Unwinding gives $T (n) = O(n log n)$:

$$\begin{aligned}{} T(n) &=2T(n/2)+cn= \\ &=2(2T(n/4)+cn/2)+cn=4T(n/4)+2cn=\\ &=4(2T(n/8)+cn/4)+2cn=8T(n/8)+3cn=\\ & \space \space \space \vdots \\ &=2^kT(n/2^k)+kcn= \\ & \space \space \space \vdots \\ &=nT(1)+log_2n \cdot cn=O(nlogn).\\ \end{aligned}$$ ...