# Master Theorem For _master [[recurrence]]_ in form of $ T(n) = aT(n/b) + f(n) $ If there exists a constant $\epsilon > 0$, or $k \ge 0$: > [!summary] Master Theorem > > 1. $f(n) = O\left(n^{\log_b a-\epsilon}\right)$, then > $T(n) = \Theta\left(n^{\log_ba}\right)$. > 2. $f(n) = \Theta\left(n^{\log_ba\lg^kn}\right)$, then > $T(n) = \Theta\left(n^{\log_ba} \lg^{k+1}n\right)$. > 3. $f(n) = \Omega\left(n^{\log_b a+\epsilon}\right)$, and $f(n)$ satisfies the > _regularity condition_ $af(n/b) \le cf(n)$ for some constant $c < 1$ and > all sufficiently large $n$, then $T(n) = \Theta(f(n))$. - $f(n)$ is a _driving function_, $n^{\log_ba}$ is the _watershed function_. ## Explanation - Watershed function characterizes the number of leaves [[asymptotic-notation|asymptotically]]. - **Case 1:** Watershed function grows _polynomially_ faster than driving function. Cost per level grows at least [[geometric-series|geometrically]] from root to leaves, the ==total cost of leaves dominates that of the internal nodes.== - **Case 2:** Driving function grows faster than watershed function by a factor of $\Theta\left(\lg^k n\right)$. ==Each level costs roughly the same.== Most of the time $k = 0$. - **Case 3:** Driving function grows _polynomially_ faster. Regularity condition is satisfied most of the time. ==Cost of root dominates.== ## Proof - Lemma 1: Cost of leaves and internal nodes. $ T(n) = \Theta\left(n^{\log_ba}\right) + \sum_{j=0}^{\left\lfloor\log_bn\right\rfloor} a^j f\left(n/b^i\right) $ - Lemma 2: Bound of the summation