Master theorem — solving recurrences T(n) = aT(n - b) + f(n): Exercises

Reminder of the three cases (the referee's rulebook):

Figure — Master theorem — solving recurrences T(n) = aT(n - b) + f(n)

Level 1 — Recognition

Goal: read off $a$ , $b$ , compute $p = lo g_{b} a$ , and name the case. No algebra beyond a logarithm.

L1.1 $T (n) = 4 T (n /2) + n$ . Find $p$ and the answer.

Recall Solution L1.1

$a = 4, b = 2 \Rightarrow p = lo g_{2} 4 = 2$ . Leaf cost $= n^{2}$ .
$f (n) = n = n^{1}$ . Since $1 < 2$ , $f$ is polynomially smaller ( $n = O (n^{2 - ϵ})$ , e.g. $ϵ = 1$ ).
Case 1 → leaves win. $T (n) = Θ (n^{2})$ .

L1.2 $T (n) = 2 T (n /2) + n$ . Name the case and give the answer.

Recall Solution L1.2

$a = 2, b = 2 \Rightarrow p = lo g_{2} 2 = 1$ . Leaf cost $= n^{1}$ .
$f (n) = n = n^{1}$ — exactly equal, $k = 0$ . Case 2 (tie).
$T (n) = Θ (n^{1} lo g^{0 + 1} n) = Θ (n lo g n)$ (this is Merge Sort).

L1.3 $T (n) = T (n /2) + 1$ . Name the case and give the answer.

Recall Solution L1.3

$a = 1, b = 2 \Rightarrow p = lo g_{2} 1 = 0$ . Leaf cost $= n^{0} = 1$ .
$f (n) = 1 = Θ (n^{0} lo g^{0} n)$ — tie with $k = 0$ . Case 2.
$T (n) = Θ (n^{0} lo g^{1} n) = Θ (lo g n)$ (this is Binary Search).

Level 2 — Application

Goal: verify a regularity condition, handle a Case 3, and a Case 1 with fractional $p$ .

L2.1 $T (n) = 2 T (n /2) + n^{2}$ . Solve, showing the regularity check.

Recall Solution L2.1

$a = 2, b = 2 \Rightarrow p = 1$ . Leaf cost $= n^{1}$ .
$f (n) = n^{2} = Ω (n^{1 + ϵ})$ with $ϵ = 1$ — polynomially bigger. Candidate Case 3.
Regularity: $a f (n / b) = 2 (\frac{n}{2})^{2} = 2 \cdot \frac{n ^{2}}{4} = \frac{n ^{2}}{2} = \frac{1}{2} f (n) \leq c f (n)$ with $c = \frac{1}{2} < 1$ . ✓
Case 3 → root wins. $T (n) = Θ (n^{2})$ .

L2.2 $T (n) = 3 T (n /2) + n$ . Solve. (This is Karatsuba Multiplication.)

Recall Solution L2.2

$a = 3, b = 2 \Rightarrow p = lo g_{2} 3 \approx 1.585$ . Leaf cost $= n^{1.585}$ .
$f (n) = n = n^{1}$ , and $1 < 1.585$ , so $n = O (n^{1.585 - ϵ})$ . Polynomially smaller.
Case 1 → leaves win. $T (n) = Θ (n^{l o g_{2} 3}) \approx Θ (n^{1.585})$ — beats schoolbook $n^{2}$ .

L2.3 $T (n) = 9 T (n /3) + n^{2}$ . Solve, showing the regularity check.

Recall Solution L2.3

$a = 9, b = 3 \Rightarrow p = lo g_{3} 9 = 2$ . Leaf cost $= n^{2}$ .
$f (n) = n^{2} = Θ (n^{2} lo g^{0} n)$ — exactly equal, $k = 0$ . Case 2.
(No regularity check needed — that is only for Case 3.)
$T (n) = Θ (n^{2} lo g n)$ .

Level 3 — Analysis

Goal: spot the log-factor gap, and cases where the naive exponent comparison misleads you.

L3.1 $T (n) = 2 T (n /2) + n lo g n$ . Solve carefully.

Recall Solution L3.1

$p = lo g_{2} 2 = 1$ . Leaf cost $= n^{1}$ .
Is $f = n lo g n$ polynomially bigger than $n$ ? For Case 3 we'd need $n lo g n = Ω (n^{1 + ϵ})$ for some $ϵ > 0$ . But $lo g n$ grows slower than any $n^{ϵ}$ , so no such $ϵ$ exists. Case 3 fails — there is only a log gap, not a polynomial gap.
Rewrite $f = Θ (n^{1} lo g^{1} n)$ , i.e. Case 2 with $k = 1$ .
$T (n) = Θ (n^{1} lo g^{1 + 1} n) = Θ (n lo g^{2} n)$ .

L3.2 $T (n) = 4 T (n /2) + n^{2} lo g n$ . Solve.

Recall Solution L3.2

$a = 4, b = 2 \Rightarrow p = 2$ . Leaf cost $= n^{2}$ .
$f = n^{2} lo g n = Θ (n^{2} lo g^{1} n)$ — Case 2 with $k = 1$ (equal up to a log factor).
$T (n) = Θ (n^{2} lo g^{1 + 1} n) = Θ (n^{2} lo g^{2} n)$ .

L3.3 $T (n) = 4 T (n /2) + n^{2} / lo g n$ . Solve.

Recall Solution L3.3

$p = 2$ , leaf cost $= n^{2}$ . Here $f = n^{2} / lo g n = n^{2} lo g^{- 1} n$ .
Case 2 requires $k \geq 0$ ; here the exponent on $lo g$ is $k = - 1 < 0$ , so basic Case 2 does not apply.
$f$ is slightly smaller than $n^{2}$ , but not by a polynomial factor, so Case 1 also fails. This falls in the gap below the tie. (Recognition point: not solvable by the three cases as stated.)
Show the WHY with a recursion tree. Level $i$ has $4^{i}$ nodes, each of size $n / 2^{i}$ , so its cost is $=4^i\cdot\frac{n^2/4^i}{\log n - i}=\frac{n^2}{\log n - i}.$$ The $4^i$ cancels — **every level costs $\dfrac{n^2}{\log n-i}$**, so we add these up.$
Summing over levels $i = 0, 1, \dots, lo g_{2} n - 1$ : $=n^2\!\!\sum_{j=1}^{\log_2 n}\frac1{j}\qquad(\text{substitute } j=\log n-i).$$ That inner sum $1+\tfrac12+\tfrac13+\cdots+\tfrac1{\log_2 n}$ is a **harmonic sum**, which grows like $\ln(\text{number of terms})=\Theta(\log\log n)$ (the log of $\log_2 n$).$
Therefore $T (n) = Θ (n^{2} lo g lo g n)$ . The extra $lo g lo g n$ is exactly that harmonic sum — Recursion Trees shows it directly; Akra–Bazzi method gives the same via its integral.

Level 4 — Synthesis

Goal: recognize when the theorem does NOT apply, and translate a real algorithm into a recurrence.

L4.1 Can the Master Theorem solve $T (n) = T (n /3) + T (2 n /3) + n$ ? If not, what do you use and what is the answer?

Recall Solution L4.1

The two subproblems have different sizes ( $n /3$ and $2 n /3$ ). The theorem's form $a T (n / b)$ assumes all $a$ subproblems are the same size $n / b$ . Master Theorem does not apply.
Use Recursion Trees or Akra–Bazzi method. Every level does $Θ (n)$ combine work (the child sizes sum to $n$ ), and the tree has $Θ (lo g n)$ levels (longest path shrinks by the $2/3$ branch each time).
$T (n) = Θ (n lo g n)$ .

L4.2 A function processes an array of size $n$ by making 7 recursive calls on subarrays of size $n /2$ , then does $Θ (n^{2})$ combine work. Write the recurrence and solve it. (This mirrors naive $7$ -way matrix ideas.)

Recall Solution L4.2

Recurrence: $T (n) = 7 T (n /2) + n^{2}$ .
$a = 7, b = 2 \Rightarrow p = lo g_{2} 7 \approx 2.807$ . Leaf cost $= n^{2.807}$ .
$f = n^{2} = n^{2}$ , and $2 < 2.807$ , so $f = O (n^{2.807 - ϵ})$ — polynomially smaller.
Case 1 → leaves win. $T (n) = Θ (n^{l o g_{2} 7}) \approx Θ (n^{2.807})$ .

L4.3 Strassen-style: $T (n) = 7 T (n /2) + n^{2.807}$ . Which case, and why is it a borderline?

Recall Solution L4.3

$p = lo g_{2} 7 \approx 2.807$ . Leaf cost $= n^{2.807}$ .
$f (n) = n^{2.807}$ is exactly $Θ (n^{p})$ (same exponent) — Case 2 with $k = 0$ .
$T (n) = Θ (n^{l o g_{2} 7} lo g n) \approx Θ (n^{2.807} lo g n)$ .
Borderline because $f$ 's exponent equals $p$ ; a hair smaller and it would be Case 1, a hair larger (polynomially) and it would be Case 3.

Level 5 — Mastery

Goal: full derivations from the geometric series, boundary reasoning, and building intuition from Geometric Series.

L5.1 For $T (n) = a T (n / b) + f (n)$ with $f = n^{c}$ , the sum of per-level costs is a geometric series with ratio $r = a / b^{c}$ . Show how the sign of $c - lo g_{b} a$ decides which case you're in, using the ratio $r$ .

Recall Solution L5.1

First, how many levels are there? Sizes shrink $n \to n / b \to n / b^{2} \to \dots$ and bottom out at $1$ when $n / b^{L} = 1$ , i.e. $L = lo g_{b} n$ . So $L$ , the number of levels, is $lo g_{b} n$ .
Level $i$ cost $= a^{i} f (n / b^{i}) = a^{i} (n / b^{i})^{c} = n^{c} (\frac{a}{b ^{c}})^{i} = n^{c} r^{i}$ with $r = a / b^{c}$ .
The total is $n^{c} \sum_{i = 0}^{L - 1} r^{i}$ where $L = lo g_{b} n$ — a Geometric Series. Its behaviour depends on $r$ :
- $r < 1$ ⟹ series converges to a constant ⟹ root dominates ⟹ $Θ (n^{c}) = Θ (f)$ → Case 3.
- $r = 1$ ⟹ every term equal, $L = lo g_{b} n$ terms ⟹ $Θ (n^{c} lo g n)$ → Case 2.
- $r > 1$ ⟹ series dominated by its last term (leaves), $= Θ (n^{l o g_{b} a})$ → Case 1.
Now translate $r$ : $r = a / b^{c}$ , so
- $r < 1 ⟺ a < b^{c} ⟺ lo g_{b} a < c$ : $f$ bigger than leaf cost → Case 3. ✓
- $r = 1 ⟺ a = b^{c} ⟺ lo g_{b} a = c$ : tie → Case 2. ✓
- $r > 1 ⟺ a > b^{c} ⟺ lo g_{b} a > c$ : $f$ smaller → Case 1. ✓
This is why the three cases exist: they are the three regimes of a geometric series.

L5.2 Solve $T (n) = 2 T (n /4) + n$ from the geometric series directly (don't just quote the case).

Recall Solution L5.2

$a = 2, b = 4 \Rightarrow p = lo g_{4} 2 = \frac{1}{2}$ , and $f = n = n^{1/2}$ , so exponent $c = \frac{1}{2}$ .
Number of levels: $L = lo g_{b} n = lo g_{4} n$ .
Level $i$ cost $= a^{i} f (n / b^{i}) = 2^{i} (\frac{n}{4 ^{i}})^{1/2} = 2^{i} \cdot \frac{n ^{1/2}}{2 ^{i}} = n^{1/2}$ . Every level costs $n$ (ratio $r = 2/ 4^{1/2} = 1$ ).
Sum the equal level-costs over all $L = lo g_{4} n$ levels: $T (n) = \sum_{i = 0}^{l o g_{4} n - 1} n = n \cdot lo g_{4} n = Θ (n lo g n) .$
So directly from the series, $T (n) = Θ (n lo g n)$ — matching Case 2 with $k = 0$ .

L5.3 Solve $T (n) = 16 T (n /4) + n!$ . Which case, and what makes $f$ "polynomially bigger"?

Recall Solution L5.3

$a = 16, b = 4 \Rightarrow p = lo g_{4} 16 = 2$ . Leaf cost $= n^{2}$ .
$f = n!$ grows faster than any polynomial $n^{2 + ϵ}$ , so certainly $f = Ω (n^{2 + ϵ})$ . Candidate Case 3.
Regularity: $a f (n / b) = 16 (n /4)!$ . Since $(n /4)!$ is astronomically smaller than $n!$ (ratio $\to 0$ ), for large $n$ we have $16 (n /4)! \leq c n!$ with $c < 1$ easily. ✓
Case 3 → root wins. $T (n) = Θ (n!)$ .

L5.4 Boundary probe: solve $T (n) = 2 T (n /2) + n / lo g n$ . Explain why neither Case 1 nor basic Case 2 fits.

Recall Solution L5.4

$p = 1$ , leaf cost $= n$ . Here $f = n / lo g n = n lo g^{- 1} n$ , i.e. $k = - 1$ .
Basic Case 2 needs $k \geq 0$ ; $k = - 1$ is outside it. And $f$ is smaller than $n$ only by a log factor, not a polynomial one, so Case 1 fails too. Gap below the tie.
Direct sum: level $i$ cost $= 2^{i} \cdot \frac{n / 2 ^{i}}{lo g ( n / 2 ^{i} )} = \frac{n}{lo g n - i}$ ; summing $i = 0.. lo g_{2} n - 1$ gives $T (n) = \sum_{i = 0}^{l o g_{2} n - 1} \frac{n}{l o g n - i} = n \sum_{j = 1}^{l o g_{2} n} \frac{1}{j} .$
The inner sum $1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{l o g _{2} n}$ is a harmonic sum (the sum of reciprocals $1/1 + 1/2 + \dots$ ), which grows like the natural log of its number of terms, i.e. $Θ (lo g (lo g_{2} n)) = Θ (lo g lo g n)$ .
Therefore $T (n) = Θ (n lo g lo g n)$ — provable by recursion tree, not by the three-case theorem.

Connections

Recursion Trees — the derivation behind L5, and the fallback for L3.3, L4.1, L5.4.
Akra–Bazzi method — solves the unequal-split cases the theorem can't (L4.1).
Geometric Series — the engine of L5.1 that produces the three cases.
Big-O, Big-Omega, Big-Theta — the "polynomially smaller/bigger" comparisons.
Merge Sort, Binary Search, Karatsuba Multiplication — appear as L1/L2 problems.

Flashcards

Solve

T (n) = 4 T (n /2) + n

p = 2

f = n = O (n^{2 - ϵ})

→ Case 1 →

Θ (n^{2})

In Case 2, what does the exponent

k

mean?

k

is the power of

lo g n

already sitting in

f

when written as

n^{p} lo g^{k} n

; the answer gains one more log:

n^{p} lo g^{k + 1} n

Solve

T (n) = 2 T (n /2) + n lo g n

Only a log gap, so it is Case 2 with

k = 1

(here

f = n^{1} lo g^{1} n

) →

Θ (n lo g^{2} n)

Why can't Master Theorem solve

T (n) = T (n /3) + T (2 n /3) + n

Subproblems differ in size; the form

a T (n / b)

needs identical sizes. Use recursion tree / Akra–Bazzi →

Θ (n lo g n)

What ratio governs which case you're in, and its formula?

r = a / b^{c}

where

c

f

's exponent;

r > 1

Case 1,

r = 1

Case 2,

r < 1

Case 3.

Solve

T (n) = 2 T (n /4) + n

p = 1/2

, every level costs

n

, and there are

lo g_{4} n

levels →

Θ (n lo g n)