Suggest edit — master theorem

Title

Name

Note

---
title: "master theorem"
type: concept
related: [Merge Sort, Recurrence Relation, Master Theorem]
source: https://www.jemoka.com/posts/kbhmaster_theorem/
confidence: high
status: active
---

A general recurrence relation solution formula. It&rsquo;s a generalization of the &ldquo;tree&rdquo; method in example 1.
intuition Every Recursion Theorem problem has a struggle between most work sitting at the &ldquo;bottom&rdquo; of the tree (number of subproblems explode, \(a &gt; b^{d}\)) vs most work sitting at the &ldquo;top&rdquo; of the tree (problem lower in the tree are smaller, \(a &lt; b^{d}\)).
constituents Consider:
\(a\): number of subproblems \(b\): input size shrink \(d\) need to do \(n^{d}\) work to merge subproblems Suppose \(a \geq 1, b&gt; 1\), and \(d\) are constants. Suppose \(T\qty(n) = aT\qty(\frac{n}{b}) + O\qty(n^{d})\), we then have:
requirements \begin{equation} T\qty(n) = \begin{cases} O\qty(n^{d}\log\qty(n)), \text{ if } a = b^{d}\\ O\qty(n^{d}), \text{ if } a &lt; b^{d}\\ O\qty(n^{\log_{b} \qty(a)}), \text{ if } a &gt; b^{d}\\ \end{cases} \end{equation}
additional information proof Suppose that \(T\qty(n) \leq a\cdot T\qty(\frac{n}{b}) + c \cdot n^{d}\). We desire the master theorem&rsquo;s statement. Consider a standard tree argument via merge sort. At each layer, the input size gets cut by \(b\), so we obtain \(\log_{b} \qty(n)\) layers of the tree.
Filling things out we get the following table:
Adding up the work of this table:
\begin{align} \sum_{t=0}^{\log_{b}n} a^{t} c \qty(\frac{n}{b^{t}})^{d} &amp;= cn^{d}\sum_{t=0}^{\log_{b}n} a^{t}\qty(\frac{1}{b^{t}})^{d} \\ &amp;= cn^{d}\sum_{t=0}^{\log_{b}\qty(n)} \qty(\frac{a}{b^{d}})^{t} \end{align}
The master theorem therefore splits equation into three components based on the ratio \(\frac{a}{b^{d}}\):
\(a = b^{d}\) So we obtain:
\begin{align} c n^{d} \sum_{t=0}^{\log _{b}\qty(n)} 1 = c n^{d} \qty(\log_{b}\qty(n)+1) = \theta\qty(n^{d}\log\qty(n)) \end{align}
\(a &lt; b^{d}\) Recall bounded geometric sum. Notice that if \(a &lt; b^{t}\), then \(\qty(\frac{a}{b^{d}})^{t}\) should be \(x^{t}, x&lt; 1\), so its bounded by a constant.
Hence:
\begin{align} c n^{d} \sum_{t=0}^{\log _{b}\qty(n)} \qty(\frac{a}{b^{d}})^{t} = cn^{d}\theta\qty(1) = \theta \qty(n^{d}) \end{align}
\(a &gt; b^{d}\) by bounded geometric sum