Master Theorem

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Recursion #◇Recursion and Iteration #◇Analysis of Algorithms #◇Data Structures #◇Time Complexity #◇Space Complexity

---

◇Overview

The Master Theorem provides a direct way to solve recurrences of the form $T(n) = aT(n/b) + f(n)$ without step-by-step expansion.

◇Key Concepts

Standard form: $T(n) = aT(n/b) + f(n)$ Three cases based on comparing $f(n)$ with $n^{\log_b a}$ Used to solve ◇Divide and Conquer recurrences quickly Cannot handle all recurrences (non-standard forms require other methods)

◇Details / Theory

Standard Form

The Master Theorem applies to recurrences of the form:
$T(n) = aT\left(\frac{n}{b}\right) + f(n)$

where:
$a \geq 1$ — number of subproblems in the recursion $b > 1$ — factor by which the input size is reduced $f(n)$ — cost of work done outside the recursive calls (divide + combine)

Critical Value

Compute $n^{\log_b a}$ — this represents the total work done by the leaves of the recursion tree.

The Three Cases

Case 1: If $f(n) = O(n^{\log_b a - \epsilon})$ for some $\epsilon > 0$
$T(n) = \Theta(n^{\log_b a})$
→ The leaf-level work dominates. The recursion tree is bottom-heavy.

Case 2: If $f(n) = \Theta(n^{\log_b a})$
$T(n) = \Theta(n^{\log_b a} \log n)$
→ Work is evenly distributed across all levels of the tree.

Case 3: If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon > 0$, and $af(n/b) \leq cf(n)$ for some $c < 1$
$T(n) = \Theta(f(n))$
→ The root-level work dominates. The recursion tree is top-heavy.

Worked Examples

Example 1: Merge Sort — $T(n) = 2T(n/2) + n$
$a = 2, b = 2 \Rightarrow n^{\log_2 2} = n^1 = n$ $f(n) = n = \Theta(n^{\log_b a})$ → Case 2 $T(n) = \Theta(n \log n)$

Example 2: Binary Search — $T(n) = T(n/2) + 1$
$a = 1, b = 2 \Rightarrow n^{\log_2 1} = n^0 = 1$ $f(n) = 1 = \Theta(1) = \Theta(n^0)$ → Case 2 $T(n) = \Theta(\log n)$

Example 3: $T(n) = 4T(n/2) + n$
$a = 4, b = 2 \Rightarrow n^{\log_2 4} = n^2$ $f(n) = n = O(n^{2-1})$ → Case 1 $T(n) = \Theta(n^2)$

Limitations

The Master Theorem does not apply when:
$f(n)$ is not polynomially comparable to $n^{\log_b a}$ (e.g., $f(n) = n \log n$ in some edge cases) The recurrence is not in the standard form (e.g., $T(n) = T(n-1) + n$) In these cases, use the ◇Recursion Tree Method or ◇Substitution Method

◇Common Pitfalls

Applying the Master Theorem to non-standard forms like $T(n) = T(n-1) + n$ — it only works for divide-type recurrences. Forgetting the regularity condition in Case 3: $af(n/b) \leq cf(n)$. Confusing which case applies — always compute $n^{\log_b a}$ first and compare.

◇Summary

TL;DR — The Master Theorem solves recurrences $T(n) = aT(n/b) + f(n)$ by comparing $f(n)$ to $n^{\log_b a}$ across three cases: leaf-heavy, balanced, or root-heavy.

◇Links

Related: ◇Divide and Conquer — ◇Recursion Tree Method — ◇Substitution Method — ◇Asymptotic Notation — ◇Big-O Notation — ◇Big-Theta Notation Source / Reference: Handout 03

◇References & Navigation

• Previous Topic: ◇Lower Bounds
• Next Topic: ◇Nested-Loops
• Related Notes: ◇Divide and Conquer, ◇Recurrences