AntInLoop

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>

---

Related Algorithms