# Master theorem

The master theorem is a cookbook method to solve recurrences that is applicable in many (but not all!) cases.

:::info
**Theorem (Master theorem).**
Let $a \geq 1$ and $b > 1$ be constants. Let $f : \mathbb N \to \mathbb R$ be a function and let $T$ be defined on the non-negative integers by the recurrence
$$T(n) = a T\left( \frac{n}{b} \right) + f(n),$$
where $\frac{n}{b}$ is meant to be either $\left \lfloor \frac{n}{b} \right \rfloor$ or $\left \lceil \frac{n}{b} \right \rceil$. Then $T(n)$ has the following asymptotic bounds:
1. If $f(n) = \mathcal O(n^{(\log_b a) - \varepsilon})$ for some constant $\varepsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$.
2. If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log_2 n)$.
3. If $f(n) = \Omega(n^{(\log_b a)+\varepsilon})$ for some constant $\varepsilon > 0$, and if $a f\left(\frac{n}{b}\right) \leq c f(n)$ for some constant $c < 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$.
:::

**Intutitions for the subcases:**
1. Splitting/recombining the subproblems is dominated by the subproblems, i.e. in the recursion tree "the work is in the leaves".
2. Splitting/recombining the subproblems is comparable to the subproblems themselves.
3. Splitting/recombining the subproblems dominates over the subproblems, i.e. in the recursion tree "the work is in the root".

:::success
**Examples.**
1. Consider $T(n) = 9T\left(\frac{n}{3}\right) + n$. We have $a = 9$, $b = 3$, $f(n)$. Thus, $n^{\log_b a} = n^{\log_3 9} = n^2$. Thus, $f(n) = n \in \mathcal O(n^{2-1}) = \mathcal O(n)$, and we can apply case 1 of the master theorem so $T(n) = \Theta(n^2)$.
2. Consider $T(n) = T\left(\frac{2n}{3}\right) + 1$. We have $a = 1$, $b = \frac{3}{2}$, $f(n) = 1$. This means $n^{\log_b a} = n^{\log_{3/2} 1} = n^0 = 1$. From the master theorem, we can apply case 2, thus $f(n) = \Theta(n^{\log_b a}) = \Theta(1)$. Thus, we get $T(n) = \Theta(\log_2 n)$.
3. Consider $T(n) = 3 T\left( \frac{n}{4} \right) + n \log_2 n$. We have $a = 3$, $b = 4$, $f(n) = n \log_2 n$, and $n^{\log_b a} = n^{\log_4 3} \in \mathcal O(n^{0.793})$. Since $f(n) = \Omega(n^{\log_4 3 + \varepsilon})$ with $\varepsilon \simeq 0.2$, we can apply case 3 of the master theorem if we can show that $f$ satisfies the regularity condition. For sufficiently large $n$, we get
$$a f \left(\frac{n}{b}\right) = 3 \frac{n}{4} \log_2 \left(\frac{n}{4}\right) \leq \frac{3}{4} n \log_2(n) = c f(n)$$ for $c = \frac{3}{4}$. Thus, by the master theorem $T(n) = \Theta(n \log_2 n)$.
:::

:::danger
**Example (Failure of applicability of the master theorem).**
Consider the recurrence $T(n) = 2 T\left( \frac{n}{2} \right) + n \log_2 n$. We might be inclined to try and apply the master theorem, case 3, here. For this, we would have $a = 2$, $b = 2$, $f(n) = n \log_2 n$ and $n^{\log_b a} = n$. We have that $f(n) = n \log_2 n \in \Omega(n)$, but this does not hold **polynomially**, i.e. we get
$$\frac{f(n)}{n^{\log_ba}} = \frac{n \log_2 n}{n} = \log_2 n$$
which is asymptotically smaller than any monomial $n^\varepsilon$.
:::