Framework and the Master Theorem

Divide-and-Conquer and the Master Theorem

Divide-and-conquer solves a problem instance by dividing it into several smaller subproblems of the same type, solving each subproblem recursively, and then combining their solutions to form a solution to the original instance.

Diagram loads as you scroll.

---

The General Divide-and-Conquer Recurrence

If an algorithm divides a problem of size $n$ into $a$ subproblems of size $n/b$, with $f(n)$ effort spent on dividing and combining:

$$T(n) = a \cdot T(n / b) + f(n)$$

where:

• $a \ge 1$: number of subproblems.
• $b > 1$: factor by which subproblem size is reduced.
• $f(n)$: non-recursive work to divide the input and combine the sub-results (often $f(n) \in \Theta(n^d)$ for $d \ge 0$).

---

The Master Theorem

The Master Theorem provides an immediate asymptotic solution for standard divide-and-conquer recurrences.

Theorem Statement

If $T(n) = a T(n / b) + f(n)$ where $f(n) \in \Theta(n^d)$ with $d \ge 0$:

$$T(n) \in \begin{cases} \Theta(n^d) & \text{if } a < b^d \\ \Theta(n^d \log n) & \text{if } a = b^d \\ \Theta(n^{\log_b a}) & \text{if } a > b^d \end{cases}$$

Intuitive Interpretation

Compare the rate of subproblem branching ($a$) with the rate of shrinkage ($b^d$):

1. $a < b^d$ (Root-dominated): The combining work at the root $f(n) = \Theta(n^d)$ dominates the work done by recursive leaves. Result is $\Theta(n^d)$.
2. $a = b^d$ (Balanced work): Work is evenly distributed across all $\log_b n$ levels of the recursion tree. Result is $\Theta(n^d \log n)$.
3. $a > b^d$ (Leaf-dominated): Subproblems multiply so rapidly that the vast majority of work is done at the leaves ($n^{\log_b a}$ base instances). Result is $\Theta(n^{\log_b a})$.

---

Master Theorem Examples & Lookup Reference

Recurrence	$a$	$b$	$f(n)$	$d$	Comparison	Complexity	Typical Algorithm
$T(n) = T(n/2) + 1$	1	2	$\Theta(1)$	0	$1 = 2^0$	$\Theta(\log n)$	Binary Search
$T(n) = 2T(n/2) + n$	2	2	$\Theta(n)$	1	$2 = 2^1$	$\Theta(n \log n)$	Merge Sort
$T(n) = 3T(n/2) + n$	3	2	$\Theta(n)$	1	$3 > 2^1$	$\Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$	Karatsuba Multiplication
$T(n) = 4T(n/2) + n$	4	2	$\Theta(n)$	1	$4 > 2^1$	$\Theta(n^{\log_2 4}) = \Theta(n^2)$	Naive D&C Multiplication
$T(n) = 7T(n/2) + n^2$	7	2	$\Theta(n^2)$	2	$7 > 2^2=4$	$\Theta(n^{\log_2 7}) \approx \Theta(n^{2.807})$	Strassen’s Matrix Mult
$T(n) = 2T(n/2) + n^2$	2	2	$\Theta(n^2)$	2	$2 < 2^2=4$	$\Theta(n^2)$	Root-dominated D&C

---

Exercises

Exercise 1

Apply the Master Theorem to solve:

$$T(n) = 8 T(n / 2) + 1000 n^2$$

State the values of $a, b, d$, the case condition, and the final complexity.

Show solution ↓Hide solution ↑

Solution

• $a = 8$
• $b = 2$
• $f(n) = 1000 n^2 \implies f(n) \in \Theta(n^2) \implies d = 2$

Compute $b^d = 2^2 = 4$. Since $a = 8 > b^d = 4$, this falls under Case 3 (Leaf-dominated):

$$T(n) \in \Theta(n^{\log_b a}) = \Theta(n^{\log_2 8}) = \Theta(n^3)$$

Exercise 2

Can the standard Master Theorem formula be directly applied to $T(n) = 2T(n/2) + n \log n$? Explain why or why not.

Show solution ↓Hide solution ↑

Solution

The standard version of the Master Theorem requires $f(n) \in \Theta(n^d)$ for a constant polynomial exponent $d$. Here, $f(n) = n \log n$, which contains an extra logarithmic factor not expressible as a single $n^d$.

Using the extended Master Theorem (Case 2 with $k = 1$):

$$T(n) = a T(n/b) + \Theta(n^{\log_b a} \log^k n)$$

Since $a = 2, b = 2 \implies n^{\log_2 2} = n^1$, this evaluates to:

$$T(n) \in \Theta(n \log^{k+1} n) = \Theta(n \log^2 n)$$