5 The Master theorem
Analyzing the time complexity of algorithms, especially recursive ones, is more often than not a non-trivial task. For a recursive algorithm, its time complexity can be written as a recurrence formula, which is generally not easy, sometimes even impossible to solve with a closed formula. In some cases, though, we can find asymptotic bounds of the solution, despite not being able to necessarily find the precise solution to the recurrence. One large class of such cases is the class of divide-and-conquer algorithms, i.e. algorithms that recursively split the problem into smaller, similarly-sized subproblems. The Master theorem puts asymptotic bounds on divide-and-conquer recurrences.
Let \(T f : \mathbb {N} \rightarrow \mathbb {N}\) be functions such that the recurrence
holds for some \(a {\gt} 0\) and \(b {\gt} 1\). Let also \(f(n) \in \Theta (n^d)\) for some \(d \ge 1\). Then the following holds:
if \(a {\lt} b^d\), then \(T(n) \in \Theta (n^d)\),
if \(a = b^d\), then \(T(n) \in \Theta (n^d \log _b{n})\) and
if \(a {\gt} b^d\), then \(T(n) \in \Theta (n^{\log _b{a}})\).
In the case where \(f\) is bounded above by \(n^d\) only above or only below, \(T\) is also bounded only above or only below by the respective function.
We prove this theorem by proving all of its cases separately.
Let \(T f : \mathbb {N} \rightarrow \mathbb {N}\) be functions such that \(T\) is monotone and the recurrence
holds for all \(n \ge n\_ 0\) for some \(a {\gt} 0\), \(n\_ 0 {\gt} 1\) and \(b {\gt} n\_ 0\). Let also \(f(n) \in O(n^d)\) for some \(d \ge 1\). The above recurrence is an upper master recurrence with parameters \((a, n\_ 0, b, d)\).
Let \(T f : \mathbb {N} \rightarrow \mathbb {N}\) be functions such that \(T\) is monotone and the recurrence
holds for all \(n \ge n\_ 0\) for some \(a {\gt} 0\), \(n\_ 0 {\gt} 1\) and \(b {\gt} n\_ 0\). Let also \(f(n) \in \Omega (n^d)\) for some \(d \ge 1\). The above recurrence is a lower master recurrence with parameters \((a, n\_ 0, b, d)\).
Let \(T\) and \(f\) form a lower master recurrence with parameters \((a, n\_ 0, b, d)\). Then \(T(n) \in O(n^{\log _b{a}} + \sum _{k=0}^{\lfloor \log _b{n} \rfloor } (\frac{a}{b^d})^k n^d)\).
To eliminate ceilings in the recurrence, we substitute \(T(n)\) with \(S(n) = T(n+b)\). Since \(T\) is monotone, \(T(n) \leq S(n) = T(n+b)\) holds for all \(n\). Therefore, an upper bound on \(S\) is also an upper bound on \(T\). We must first show that \(S\) follows the recurrence of \(T\) without ceilings. By the assumption that \(b\) is a natural number such that \(b {\gt} 1\), we have the inequality
Therefore, by monotonicity of \(T\) we have
which captures the wanted recurrence. Integer division here is defined as the floor of real-number division. By substituting the inequality into itself repeatedly, we get
Let \(N\) be the integer such that for all \(n \geq N \geq n\_ 0\), the inequality \(f(n) \leq C n^d\) holds. Such \(N\) exists because \(f(n) \in O(n^d)\). We set \(k = \lfloor \log _b{\frac{n}{N}} \rfloor \). This choice of \(k\) allows the inequality \(n \geq N * b^k\) to hold for large enough \(n\).
Consider both sum parts on the right side of the Equation ??. For the first part, we notice that \(n^{\log _b{a}} = a^{\log _b{n}}\). Expand \(k\) in the exponent and apply monotonicity:
This implies \(a^k \in O(n^{\log _b{a}})\). We also need \(S(\frac{n}{b^k})\) to be bounded by a constant. We show that \(S(\frac{n}{b^k}) \leq S(N*b)\). Since \(S\) is monotone, this is equivalent to showing \(\frac{n}{b^k} \leq N*b\). We rewrite the left side as
Then, rewrite the right side as \(N*b = b^{\log _b{N} + 1}\). With both sides written as exponents of \(b\), we only need to prove
By swapping terms, we get
which holds for all real numbers.
For the second part, the inequality \(k \leq \lfloor \log _b{n} \rfloor \) holds by monotonicity of logarithms. As geometric sums are monotone in the exponent, we get \(\sum _{i=0}^k (\frac{a}{b^d})^i n^d \in O(\sum _{i=0}^{\lfloor \log _b{n} \rfloor } (\frac{a}{b^d})^i n^d)\).
Let \(T\) and \(f\) form a lower master recurrence with parameters \((a, n\_ 0, b, d)\), where \(a {\lt} b^d\). Then \(T(n) \in O(n^d)\).
First, we apply Lemma 122. Since \(a {\lt} b^d\), we have \(\frac{a}{b^d} {\lt} 1\). By basic properties of geometric sums, we get
which proves the upper bound.
Let \(T\) and \(f\) form an upper master recurrence with parameters \((a, n\_ 0, b, d)\), where \(a = b^d\). Then \(T(n) \in O(n^d \log _b{n})\).
After applying Lemma 122, we note that \(\log _b{a} = d\) and then the proof boils down to showing that the geometric sum is bounded by \(\log _b{n}\). Since \(\frac{a}{b^d} = 1\), the geometric sum equals \(\lfloor \log _b{n} \rfloor \), which is obviously bounded by \(\log _b{n}\).
Let \(T\) and \(f\) form an upper master recurrence with parameters \((a, n\_ 0, b, d)\), where \(a {\gt} b^d\). Then \(T(n) \in O(n^{\log _b{a}})\).
After applying Lemma 122, the left side of the sum if trivially bounded by \(n^{\log _b{a}}\). We are left with the right summand, which we transform using an inequality involving the geometric sum:
Since \(a {\gt} b^d\), \(\frac{a}{b^d} {\gt} 1\) holds, so \(\frac{1}{\frac{a}{b^d} - 1} {\gt} 0\), which proves boundedness by \(n^{\log _b{a}}\).
Let \(T\) and \(f\) form an upper master recurrence with parameters \((a, n\_ 0, b, d)\). Then \(T(n) \in \Omega (\sum _{k=0}^{\lfloor \log _b{n} \rfloor } (\frac{a}{b^d})^k n^d)\).
We consider the recurrence formula with ceilings replaced by floors. If the resulting inequality holds, then so does the master recurrence, so it suffices to prove the lower bound for this inequality.
By substituting the inequality into itself repeatedly, we get
We set \(k = \lfloor \log _b{n} \rfloor \). This choice of \(k\) allows the inequality \(n \geq b^k\) to hold for large enough \(n\). Here \(C\) is a positive constant such that \(f(n) \geq C n^d\) for all \(n \geq n\_ 0\). Such a constant exists, because \(f(n) \in \Omega (n^d)\) implies \(f(n) \geq C\_ 0 n^d\) for some \(C\_ 0 {\gt} 0\) for all \(n \geq N\) for some \(N\). For \(n\_ 0 \leq n \leq N\), The argument is as follows. The set of natural numbers between \(n\_ 0\) and \(N\) is finite, so the image of \(f\) on this set has a maximal element \(M\). We then have \(f(n) \geq \frac{M}{N^d} n^d\).
The second summand in the right side of Equation ?? is trivially bounded above by \(\sum _{k=0}^{\lfloor \log _b{n} \rfloor } (\frac{a}{b^d})^k n^d\). This is sufficient to prove the upper bound od \(T(n)\) as the left summand is non-negative.
Let \(T\) and \(f\) form a lower master recurrence with parameters \((a, n\_ 0, b, d)\). Then \(T(n) \in \Omega (n^d)\).
Since \(T(n) \geq f(n)\) for all \(n \ge n\_ 0\), the lower bound follows directly from \(f(n) \in \Omega (n^d)\).
Let \(T\) and \(f\) form a lower master recurrence with parameters \((a, n\_ 0, b, d)\) where \(a = b^d\). Then \(T(n) \in \Omega (n^d \log _b{n})\).
By Lemma 126, it suffices to show that \(\sum _{i=0}^{\lfloor \log _b{n} \rfloor } (\frac{a}{b^d})^i \in \Omega (\log _b{n})\). Applying equality \(a = b^d\), the sum simplifies to
Let \(T\) and \(f\) form an upper master recurrence with parameters \((a, n\_ 0, b, d)\) where \(a {\gt} b^d\). Then \(T(n) \in \Omega (n^{\log _b{a}})\).
By Lemma 126, we need to show that \(\sum _{i=0}^{\lfloor \log _b{n} \rfloor } (\frac{a}{b^d})^i n^d \in \Omega (n^{\log _b{a}})\). By \(a {\gt} b^d\), we have
which proves the bound.
Let \(T\) and \(f\) form an upper and lower master recurrence with parameters \((a, n\_ 0, b, d)\) where \(a {\lt} b^d\). Then \(T(n) \in \Theta (n^d)\).
Let \(T\) and \(f\) form an upper and lower master recurrence with parameters \((a, n\_ 0, b, d)\) where \(a = b^d\). Then \(T(n) \in \Theta (n^d \log _b{a})\).
Let \(T\) and \(f\) form an upper and lower master recurrence with parameters \((a, n\_ 0, b, d)\) where \(a {\gt} b^d\). Then \(T(n) \in \Theta (n^{\log _b{n}})\).