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

What the symbols mean (WHAT)

The number $n^{\log_b a}$ is the total cost of the leaves. Everything depends on comparing your combine-cost $f(n)$ to it.

Deriving it from scratch (HOW — never just trust the formula)

Unroll the recursion into a tree.

Level 0 (root): 1 node, work $f(n)$ .
Level 1: $a$ nodes, each work $f(n/b)$ → total $a\,f(n/b)$ .
Level $i$ : $a^i$ nodes, each size $n/b^i$ , work $a^i f(n/b^i)$ .
Last level: size shrinks to 1 when $n/b^L = 1 \Rightarrow L = \log_b n$ .

Now count the leaves. The number of leaves is $a^{\log_b n} = n^{\log_b a} = n^{c_{\text{crit}}}.$ Why? Use $a^{\log_b n} = (b^{\log_b a})^{\log_b n} = b^{\log_b a \cdot \log_b n} = (b^{\log_b n})^{\log_b a} = n^{\log_b a}$ . So leaf cost $= \Theta(n^{\log_b a})$ .

The sum is essentially a geometric series comparing $f(n)$ to $n^{\log_b a}$ :

If $f$ is smaller ( $f = O(n^{\log_b a - \epsilon})$ ): the series grows downward, leaves dominate → $T(n)=\Theta(n^{\log_b a})$ .
If $f$ is equal ( $f = \Theta(n^{\log_b a})$ ): every level costs about the same, and there are $\log_b n$ levels → multiply by $\log n$ .
If $f$ is bigger ( $f = \Omega(n^{\log_b a + \epsilon})$ ): the root dominates → $T(n)=\Theta(f(n))$ (needs a regularity check so the series actually converges to the root).

The three cases (the 20% you must memorize)

Formula Master Theorem

Let $c_{\text{crit}} = \log_b a$ . Then:

Case 1 (leaves win): if $f(n) = O(n^{c_{\text{crit}} - \epsilon})$ for some $\epsilon>0$ , $T(n) = \Theta\!\left(n^{\log_b a}\right).$

Case 2 (tie): if $f(n) = \Theta(n^{c_{\text{crit}}}\log^k n)$ with $k\ge 0$ , $T(n) = \Theta\!\left(n^{\log_b a}\,\log^{k+1} n\right).$

Case 3 (root wins): if $f(n) = \Omega(n^{c_{\text{crit}} + \epsilon})$ and the regularity condition $a\,f(n/b) \le c\,f(n)$ for some $c<1$ holds, $T(n) = \Theta\!\left(f(n)\right).$

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

Forecast-then-Verify worked examples

Where it BREAKS (Steel-man your mistakes)

Quick decision recipe (80/20)

Compute $p=\log_b a$ and the leaf cost $n^p$ .
Polynomially smaller $f$ → Case 1 → answer $n^p$ .
Equal (up to $\log^k$ ) → Case 2 → answer $n^p\log^{k+1}n$ .
Polynomially bigger $f$ + regularity → Case 3 → answer $f(n)$ .
Only a log gap between cases → not basic Master; use extended Case 2.

Recall Feynman: explain to a 12-year-old (click to reveal)

Imagine a chore that you split among friends. Each round you hand each friend a smaller chore, but you also do some sorting work yourself. Two costs fight: the giant pile of tiny chores at the bottom vs the big sorting you do at the top. The Master Theorem is just a referee: count how fast chores multiply ( $a$ ) versus how fast they shrink ( $b$ ). If tiny chores swamp you, the answer is the leaf cost. If your own sorting swamps you, the answer is the top cost. If they're a tie, you pay the same on every floor of the building, so you multiply by the number of floors ( $\log n$ ).

Connections

Recursion Trees — the visual derivation the Master Theorem summarizes.
Akra–Bazzi method — generalization for unequal subproblems / non-constant splits.
Big-O, Big-Omega, Big-Theta — the asymptotic comparison machinery.
Merge Sort, Karatsuba Multiplication, Binary Search — direct applications.
Geometric Series — why the three cases exist (increasing/flat/decreasing series).

Flashcards

What three quantities define the Master Theorem recurrence?

a

= number of subproblems,

b

= shrink factor (

n\to n/b

f(n)

= work outside recursion (split+combine).

What is the critical exponent and what does

n^{\log_b a}

represent?

c_{\text{crit}}=\log_b a

;

n^{\log_b a}

is the total cost of the leaves of the recursion tree.

State Case 1 of the Master Theorem.

f(n)=O(n^{\log_b a-\epsilon})

, then

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

(leaves win).

State Case 2 (extended).

f(n)=\Theta(n^{\log_b a}\log^k n)

, then

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

State Case 3 and its extra condition.

f(n)=\Omega(n^{\log_b a+\epsilon})

AND

a f(n/b)\le c f(n)

for some

c<1

, then

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

Why does Case 2 multiply by

\log n

Every level costs the same (

\Theta(n^{\log_b a})

) and there are

\log_b n

levels, so total = level cost × number of levels.

Solve

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

c_{\text{crit}}=1

f=n=\Theta(n^1)

→ Case 2 →

\Theta(n\log n)

Solve

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

c_{\text{crit}}=0

f=1=\Theta(n^0)

→ Case 2 →

\Theta(\log n)

(binary search).

Why can't basic Master Theorem solve

T(n)=2T(n/2)+n\log n

n\log n

exceeds

n

only by a log factor, not a polynomial factor — falls in the gap; extended Case 2 gives

\Theta(n\log^2 n)

Why is the number of leaves

n^{\log_b a}

a^{\log_b n} = (b^{\log_b a})^{\log_b n} = n^{\log_b a}

When does the Master Theorem NOT apply?

Non-constant

a,b

; unequal subproblem sizes (e.g.

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

); non-polynomial gaps; negative

f

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, Master Theorem ka funda simple hai: jab bhi koi divide-and-conquer algorithm likhte ho, woh problem ko chhote tukdo mein todta hai. Recurrence aati hai $T(n)=aT(n/b)+f(n)$ — yahan $a$ matlab kitne subproblems banaye, $b$ matlab har baar input kitna chhota hua ( $n/b$ ), aur $f(n)$ matlab divide aur combine ka jo extra kaam karna pada wahi level pe.

Ab pura khel ek race hai. Ek taraf hai leaves ka total cost jo nikalta hai $n^{\log_b a}$ , aur doosri taraf hai tumhara $f(n)$ . Dono ko compare karo. Agar $f(n)$ chhota hai (polynomially), toh leaves jeet gaye → answer $\Theta(n^{\log_b a})$ (Case 1). Agar dono barabar hain, toh har level pe same kaam, aur $\log_b n$ levels — isliye ek extra $\log n$ multiply hota hai → Case 2. Agar $f(n)$ bada hai aur regularity condition pass karta hai, toh root jeet gaya → answer $\Theta(f(n))$ (Case 3).

Yaad rakhne ka tarika: "LET" — Leaves, Equal, Top. Merge sort dekho: $2T(n/2)+n$ , yahan $\log_2 2 = 1$ , aur $f=n=n^1$ , dono barabar → Case 2 → $n\log n$ . Bas itna dhyaan rakho ki "bada" ya "chhota" ka matlab hai polynomially (yaani $n^\epsilon$ ka farak), sirf $\log$ ka farak nahi. Agar sirf log ka gap hai (jaise $n\log n$ vs $n$ ), toh basic theorem fail ho jaata hai — extended Case 2 use karna padta hai. Yeh chhoti si galti exams mein bahut log karte hain!

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

What the symbols mean (WHAT)

Deriving it from scratch (HOW — never just trust the formula)

The three cases (the 20% you must memorize)

Forecast-then-Verify worked examples

Where it BREAKS (Steel-man your mistakes)

Quick decision recipe (80/20)

Connections

Flashcards

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Complexity Analysis

Connections