1.3Solving recurrences
The idea
A recurrence expresses the cost of a recursive algorithm in terms of smaller inputs. Solve it by guessing and checking, or by summing the work in each level of the recursion tree.
Think of it like this: A chain of messengers: each one hands part of the work to others, and you add up what everyone did.
Why it exists
T(n) = T(n − 1) + n, T(√n) + 1 and unequal splits are not covered by the Master theorem, but they show up in GATE.
How it works
- Write the recurrence, with a base case T(1) = 1.
- Expand a few levels or draw the recursion tree.
- Add the work in each level and the number of levels.
- Confirm by induction or by checking that T(n)/guess settles near a constant.
Worked example: T(n) = T(n/3) + T(2n/3) + n
Every level of the tree costs at most n, and the longest path shrinks by 2/3 each step, so there are log_{3/2} n levels: Θ(n log n).
Now play with it
- →Pick each recurrence and watch the ratio column settle.
- →Try T(n) = T(n − 1) + T(n − 2) + 1: the ratio against 1.618ⁿ is constant.
| n | T(n) | guess n log n | T(n) / guess |
|---|---|---|---|
| 16 | 80 | 64 | 1.250 |
| 256 | 2,304 | 2,048 | 1.125 |
| 4,096 | 53,248 | 49,152 | 1.083 |
| 65,536 | 11,14,112 | 10,48,576 | 1.063 |
| 10,48,576 | 2,20,20,096 | 2,09,71,520 | 1.050 |
If the last column settles near a constant, the guess is the right Θ. If it keeps growing, the guess is too small; if it keeps shrinking, too large. T(√n) + 1 reaches log log n because each step squares the shrinking.
Check yourself
T(n) = T(√n) + 1 gives
Exam notes (the dense version)
A recursive algorithm gives a recurrence T(n). Three tools: substitution (guess then prove by induction), recursion tree (sum the work per level) and the Master theorem. Common ones: T(n) = T(n − 1) + n → Θ(n²); T(n) = T(n − 1) + 1 → Θ(n); T(n) = 2T(n − 1) + 1 → Θ(2ⁿ); T(n) = T(n/2) + 1 → Θ(log n); T(n) = T(√n) + 1 → Θ(log log n); T(n) = T(n/3) + T(2n/3) + n → Θ(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.