Chapter 2: Master Theorem

Source files used: Matrix Multiplication (Recitation 1, Sections 3.1, 3.2, 3.4), Convex_hull (Lecture 2 notes, D&C paradigm and convex hull recurrence), MIT6_046JS15_pset1 (Exercise 1-2 as practice); textbook Chapter 4 (chap4, Section 4.5) as support. No worked examples are included.

1. Big Picture

The master theorem is a cookbook for divide-and-conquer recurrences with equal-size subproblems.

The Recurrences guide asks: how do you solve a recurrence in general? This guide asks: when the recurrence has the form $aT(n/b)+f(n)$ , how do you read off the answer without a proof?

\boxed{\text{Compare }f(n)\text{ with }n^{\log_b a}\text{, pick the case, write }\Theta(\cdot).}

What you need:

the general form and the watershed function $n^{\log_b a}$ ,
the three cases, including the $\lg^k n$ version of case 2,
the regularity condition for case 3,
the gaps where the theorem does not apply.

2. Core Ideas

2.1 The Form It Solves

T(n)=aT(n/b)+f(n)

$a$ : number of subproblems ( $a\ge1$ in the lecture paradigm),
$n/b$ : size of each subproblem ( $b>1$ ),
$f(n)$ : work to divide and combine (the lecture writes “[work for merge]”); the textbook calls it the driving function.

Floors and ceilings in $n/b$ do not change the answer, so ignore them.

2.2 The Watershed Function

n^{\log_b a}

This is the total cost of the leaves of the recursion tree: there are $a^{\log_b n}=n^{\log_b a}$ leaves. Every case compares $f(n)$ against this function.

2.3 Recursion-Tree Intuition

Case 1: cost per level grows geometrically toward the leaves. Leaves dominate.
Case 2: every level costs about the same, and there are $\Theta(\lg n)$ levels. Multiply by $\lg n$ .
Case 3: cost per level drops geometrically from the root. Root dominates.

The recitation suggests drawing the tree for $T(n)=4T(n/2)+\Theta(n^2)$ to see why the extra log factor appears when the two functions match: each of the $\lg n$ levels does $\Theta(n^2)$ work.

2.4 “Polynomially” Larger or Smaller

Cases 1 and 3 need a gap of at least $n^\epsilon$ for some constant $\epsilon>0$ . Being larger or smaller by only a log factor is not enough.

Example (textbook): $4T(n/2)+n^{1.99}$ . Watershed is $n^2$ , and $n^{1.99}$ is smaller by $n^{0.01}$ , so case 1 applies with $\epsilon=0.01$ .

2.5 Regularity Condition

Case 3 also needs

af(n/b)\le c\,f(n)\quad\text{for some constant }c<1\text{ and all large }n

It says the root really dominates: the combined work one level down is a constant fraction smaller. Most polynomial driving functions satisfy it.

3. Main Governing Equations and Formulas

3.1 Case 1: Leaves Dominate

If $f(n)=O(n^{\log_b a-\epsilon})$ for some constant $\epsilon>0$ :

T(n)=\Theta(n^{\log_b a})

Use when $f(n)$ is polynomially smaller than the watershed.

3.2 Case 2: Balanced (with $\lg^k n$ )

If $f(n)=\Theta(n^{\log_b a}\lg^k n)$ for some constant $k\ge0$ :

T(n)=\Theta(n^{\log_b a}\lg^{k+1}n)

The most common form is $k=0$ :

f(n)=\Theta(n^{\log_b a})\;\Rightarrow\;T(n)=\Theta(n^{\log_b a}\lg n)

Use when $f(n)$ matches the watershed up to a polylog factor. Add exactly one extra $\lg n$ .

Recitation check: $4T(n/2)+\Theta(n^2\lg n)$ is $\Theta(n^2\lg^2 n)$ , not $\Theta(n^2\lg n)$ .

3.3 Case 3: Root Dominates

If $f(n)=\Omega(n^{\log_b a+\epsilon})$ for some constant $\epsilon>0$ , and $af(n/b)\le cf(n)$ for some $c<1$ and all large $n$ :

T(n)=\Theta(f(n))

Use when $f(n)$ is polynomially larger than the watershed. Always state the regularity check.

3.4 Where the Theorem Fails

The theorem says nothing when:

$f(n)$ is smaller than the watershed, but only by a log factor (gap between cases 1 and 2),
$f(n)$ is larger than the watershed by more than a polylog but less than a polynomial (gap between cases 2 and 3),
case 3 holds except for regularity,
$f(n)$ and $n^{\log_b a}$ cannot be compared,
the recurrence is not of the form $aT(n/b)+f(n)$ (unequal splits, $T(n-1)$ ).

Recitation and textbook example of a gap:

T(n)=2T(n/2)+\Theta\!\left(\frac{n}{\lg n}\right)

Watershed $n$ ; $n/\lg n$ is smaller, but not polynomially. Case 2 would need $k=-1$ , and $k$ must be $\ge0$ . The textbook gives the answer $\Theta(n\lg\lg n)$ , found by other methods.

3.5 Course Recurrences Solved by the Master Theorem

Merge sort and D&C convex hull:

T(n)=2T(n/2)+\Theta(n)=\Theta(n\lg n)\qquad\text{(case 2)}

Convex hull with the naive $O(n^2)$ tangent search:

T(n)=2T(n/2)+\Theta(n^2)=\Theta(n^2)\qquad\text{(case 3)}

Recursive block matrix multiplication:

T(n)=8T(n/2)+\Theta(1)=\Theta(n^3)\qquad\text{(case 1)}

Strassen:

T(n)=7T(n/2)+\Theta(n^2)=\Theta(n^{\lg7})\approx\Theta(n^{2.807})\qquad\text{(case 1)}

Binary search (textbook):

T(n)=T(n/2)+\Theta(1)=\Theta(\lg n)\qquad\text{(case 2)}

Use these as anchors: if an exam recurrence looks like one of them, the case is probably the same.

3.6 Textbook Examples Worth Memorizing

T(n)=9T(n/3)+n\;\Rightarrow\;\Theta(n^2)\qquad\text{(case 1)}

T(n)=T(2n/3)+1\;\Rightarrow\;\Theta(\lg n)\qquad\text{(case 2, watershed }n^0=1)

T(n)=3T(n/4)+n\lg n\;\Rightarrow\;\Theta(n\lg n)\qquad\text{(case 3, }c=3/4)

T(n)=2T(n/2)+n\lg n\;\Rightarrow\;\Theta(n\lg^2 n)\qquad\text{(case 2, }k=1)

The last one is a classic trap: it is not case 3, because $n\lg n$ is only a log factor above $n$ .

4. Problem-Solving Workflow

Check the form $aT(n/b)+f(n)$ with constants $a\ge1$ , $b>1$ . If not, go to the Recurrences guide.
Compute the watershed $n^{\log_b a}$ . Write $\log_b a$ as a decimal if it is not an integer.
Compare $f(n)$ $f (n)$ with the watershed:
- polynomially smaller → case 1,
- equal up to $\lg^k n$ , $k\ge0$ → case 2,
- polynomially larger → case 3.
For case 3, verify $af(n/b)\le cf(n)$ with an explicit $c<1$ .
Write the answer as $\Theta(\cdot)$ .
If $f(n)$ falls in a gap, say so and switch to substitution or a recursion tree.

Practice: Problem Set 1, Exercise 1-2 (a) to (f). Section 6.2 lists the answers to check yourself.

5. Decision Rules / Decision Trees

5.1 Can I Use the Master Theorem?

Subproblems all size $n/b$ with constant $a$ , $b$ ? → yes, continue

Unequal sizes like $T(n/5)+T(7n/10+6)$ ? → no: substitution or recursion tree (Medians, Recurrences guides)

Subtract-by-one like $T(n-1)+\Theta(n)$ ? → no: unroll the sum

Argument is $\sqrt{n}$ ? → change variables first ( $m=\lg n$ ), then use the master theorem on $S(m)$

5.2 Which Case?

$f(n)=O(n^{\log_b a-\epsilon})$ ? → case 1, $\Theta(n^{\log_b a})$

$f(n)=\Theta(n^{\log_b a}\lg^k n)$ , $k\ge0$ ? → case 2, $\Theta(n^{\log_b a}\lg^{k+1}n)$

$f(n)=\Omega(n^{\log_b a+\epsilon})$ AND $af(n/b)\le cf(n)$ , $c<1$ ? → case 3, $\Theta(f(n))$

Only a log factor below the watershed? → gap, theorem does not apply

6. Important Tables / Correlations Needed

6.1 Three Cases at a Glance

Case	Condition on $f(n)$	$T(n)$	Tree picture
1	$O(n^{\log_b a-\epsilon})$	$\Theta(n^{\log_b a})$	leaves dominate
2	$\Theta(n^{\log_b a}\lg^k n)$ , $k\ge0$	$\Theta(n^{\log_b a}\lg^{k+1}n)$	all levels equal
3	$\Omega(n^{\log_b a+\epsilon})$ + regularity	$\Theta(f(n))$	root dominates

6.2 Problem Set 1, Exercise 1-2 (a) to (f): Answer Check

Recurrence	Watershed	Case	Answer
$4T(n/4)+5n$	$n$	2	$\Theta(n\lg n)$
$4T(n/5)+5n$	$n^{\log_5 4}\approx n^{0.86}$	3	$\Theta(n)$
$5T(n/4)+4n$	$n^{\log_4 5}\approx n^{1.16}$	1	$\Theta(n^{\log_4 5})$
$25T(n/5)+n^2$	$n^2$	2	$\Theta(n^2\lg n)$
$4T(n/5)+\lg n$	$n^{\log_5 4}$	1	$\Theta(n^{\log_5 4})$
$4T(n/5)+\sqrt{n}\lg^5 n$	$n^{\log_5 4}$	1	$\Theta(n^{\log_5 4})$

Parts (g) to (j) need a change of variables or unequal splits; see the Recurrences guide.

7. Key Takeaways

Form: $T(n)=aT(n/b)+f(n)$ , $a\ge1$ , $b>1$ , equal-size subproblems only.
Always compute the watershed $n^{\log_b a}$ first.
Case 1: $f$ polynomially smaller → $\Theta(n^{\log_b a})$ .
Case 2: $f=\Theta(n^{\log_b a}\lg^k n)$ → multiply by one more $\lg n$ .
Case 3: $f$ polynomially larger and regular → $\Theta(f(n))$ .
A log-factor difference is not polynomial: $2T(n/2)+n\lg n$ is case 2, $\Theta(n\lg^2 n)$ .
$2T(n/2)+n/\lg n$ falls in a gap; the theorem cannot be used.
Strassen $7T(n/2)+\Theta(n^2)$ is case 1: $\Theta(n^{\lg 7})$ .
Convex hull and merge sort $2T(n/2)+\Theta(n)$ are case 2: $\Theta(n\lg n)$ .
Median finding’s $T(n/5)+T(7n/10+6)+\Theta(n)$ is not a master recurrence.