The Master Theorem (Divide-and-Conquer Recurrences)
The Master Theorem gives immediate asymptotic solutions for divide-and-conquer recurrences T(n) = a T(n / b) + f(n) by comparing the leaf growth n^(log_b a) against the combine cost f(n).
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
The Master Theorem
For any divide-and-conquer recurrence of the form:
$T(n) = a\,T\!\left(\frac{n}{b}\right) + f(n), \qquad a \ge 1,\ b > 1$
let $c_{\text{crit}} = \log_b a$ (the leaf-count exponent). Compare $f(n)$ against $n^{c_{\text{crit}}}$:
| Case | Condition | Solution $T(n)$ | Classic Example |
| :--- | :--- | :--- | :--- |
| Case 1 (Leaf-Heavy) | $f(n) = O(n^{c_{\text{crit}} - \epsilon})$ | $\Theta(n^{\log_b a})$ | Strassen's: $7T(n/2) + n^2 \implies \Theta(n^{\log_2 7})$ |
| Case 2 (Balanced) | $f(n) = \Theta(n^{c_{\text{crit}}} \log^k n)$ ($k \ge 0$) | $\Theta(n^{\log_b a} \log^{k+1} n)$ | Merge Sort: $2T(n/2) + n \implies \Theta(n \log n)$ |
| Case 3 (Root-Heavy) | $f(n) = \Omega(n^{c_{\text{crit}} + \epsilon})$ + regularity | $\Theta(f(n))$ | $2T(n/2) + n^2 \implies \Theta(n^2)$ |
---
Interactive Classifier in C++
<details>
<summary>Show C++ Solution (Master Theorem Classifier)</summary>
#include <cmath>
#include <iostream>
#include <string>
// Classify T(n) = a * T(n / b) + Theta(n^d)
std::string classifyMaster(double a, double b, double d) {
double c = std::log(a) / std::log(b);
const double eps = 1e-9;
if (d < c - eps) return "Case 1: Theta(n^" + std::to_string(c) + ")";
if (std::abs(d - c) <= eps) return "Case 2: Theta(n^" + std::to_string(d) + " log n)";
return "Case 3: Theta(n^" + std::to_string(d) + ")";
}
int main() {
std::cout << classifyMaster(2, 2, 1) << "\n"; // Merge Sort -> Case 2
std::cout << classifyMaster(7, 2, 2) << "\n"; // Strassen -> Case 1
std::cout << classifyMaster(2, 2, 2) << "\n"; // Root-heavy -> Case 3
return 0;
}
</details>
---