11 — Master Theorem | DAA Visual Tutorial

Quick Rule — Master Theorem

Concept First

Master Theorem is used to solve recurrences of the form T(n) = aT(n/b) + f(n). The key idea is to compare the extra work f(n) with the boundary function n^log_b(a).

3-Step Recipe

Identify: a = number of subproblems, b = input shrink factor, f(n) = non-recursive work
Compute boundary: p = log_b(a), boundary = n^p
Compare: Compare f(n) with n^p

What is k ? (Very Important)

k is the power of log n already present in f(n).

Examples:

f(n) = n → no log term → k = 0
f(n) = n log n → one log → k = 1
f(n) = n log² n → two logs → k = 2

🟢 Case 1 — f(n) is smaller than boundary

If f(n) = O( n^{p − ε} ) for some ε > 0

T(n) = Θ( n^p )

👉 Smaller work per level, leaves dominate

🟡 Case 2 — f(n) matches the boundary

If f(n) = Θ( n^p · log^k n )
(k = number of log factors already in f(n))

T(n) = Θ( n^p · log^k+1 n )

👉 Each recursion level contributes equally → one extra log

🔴 Case 3 — f(n) is bigger than boundary

If f(n) = Ω( n^{p + ε} ) for some ε > 0

T(n) = Θ( f(n) )

👉 Root work dominates (regularity condition required)

Interactive Solver

Auto Case

f(n)

Show steps

p = log_b(a)

—

n^p

—

Detected Case

—

Final Result

—

Recursion Tree Intuition

Why it works

LevelCost(i) = a^i · f(n / b^i)

Height is about log_b(n). Total cost depends on which levels dominate.

Case intuition

Case 1: leaves dominate → Θ(n^p)
Case 2: each level same → extra log factor
Case 3: root dominates → Θ(f(n))

11 — Master Theorem

Quick Rule — Master Theorem

Interactive Solver

Steps

Examples (Click to Load)

Recursion Tree Intuition

Mini Quiz