1.4Master theorem
The idea
The Master theorem solves T(n) = a·T(n/b) + Θ(nᵏ logᵖ n) by comparing the leaf cost with the root cost.
Think of it like this: A tournament: if the early rounds cost more than the final, the first rounds dominate, and vice versa.
Why it exists
It is the fastest way to solve divide-and-conquer recurrences, and GATE asks it directly almost every year.
How it works
- Compute c = log_b a.
- c > k: the leaves dominate, T = Θ(n^c).
- c = k: every level costs the same, T = Θ(nᵏ logᵖ⁺¹ n).
- c < k: the root dominates, T = Θ(nᵏ logᵖ n).
Worked example: T(n) = 4T(n/2) + n
log₂ 4 = 2 > 1 = k, so Θ(n²). Compare: 2T(n/2) + n gives n log n; T(n/2) + n gives n.
Now play with it
- →Press the Strassen button: 7 subproblems of half size give Θ(n^2.81).
- →Set a = 2, b = 2, k = 1, p = 1 and see log² n appear.
T(n) = a · T(n / b) + Θ( nk · logp n )
log_b a = 1 equals k = 1: every level costs about the same, and there are log n levels
| level | subproblems a^i | size n / b^i (n = 1024) | work at the level |
|---|---|---|---|
| 0 | 1 | 1024 | 1,024 |
| 1 | 2 | 512 | 1,024 |
| 2 | 4 | 256 | 1,024 |
| 3 | 8 | 128 | 1,024 |
| 4 | 16 | 64 | 1,024 |
| 5 | 32 | 32 | 1,024 |
Level work shrinking down the table: root dominates (Case 3). Growing: leaves dominate (Case 1). Staying the same: Case 2, multiply by the number of levels.
Check yourself
T(n) = 3T(n/2) + n has solution
Exam notes (the dense version)
For T(n) = a·T(n/b) + Θ(nᵏ logᵖ n) with a ≥ 1, b > 1: compare log_b a with k. If log_b a > k then Θ(n^(log_b a)). If equal then Θ(nᵏ logᵖ⁺¹ n). If less then Θ(nᵏ logᵖ n). It does not apply when a is not a constant, when the subproblems have different sizes, or when f(n) is not polynomially related (e.g. n / log n).
Previous year questions: Asymptotic Analysis & Recurrences (16)
PYQs are grouped by topic, so this is the full set for Asymptotic Analysis & Recurrences; try the ones that match this subtopic. Open all 16 on the topic page.