Recurrence Relations

CSS Computer Science (Optional) — Paper-I, Section-B, Topic IV. Companion page to Recursion — that page introduces recursion itself and works the Substitution Method on two examples. This page catalogs every method for solving a recurrence relation (Substitution, Recursion Tree, Master Theorem, Characteristic Equation) side by side, works the two board-example recurrences in full, and closes with the most frequently tested question pattern.

What Is a Recurrence Relation?

• A recurrence relation defines a function's value at n in terms of its own value(s) at smaller input(s) — $T(n-1)$, $T(n/2)$, $T(n-1)+T(n-2)$, etc. — together with one or more base case(s) that stop the chain.
• General shape:

$$T(n) = \begin{cases} c & \text{if } n = \text{base} \\ f\big(T(\text{smaller inputs})\big) & \text{if } n > \text{base} \end{cases}$$

• Why it matters for CSS/FPSC: a recursive algorithm's running time can only naturally be expressed as a recurrence — you cannot read its Big-O off the code directly the way you can for loops. Solving the recurrence is the step that converts "the code calls itself" into an actual O() answer.
• Solving a recurrence means finding its closed-form solution — an explicit formula for $T(n)$ with no $T(\cdot)$ on the right-hand side — which is then simplified into a Big-O / Θ class.

Exam angle: examiners phrase this two ways — "solve the recurrence T(n) = ... using the substitution method" (they name the method) or "find the time complexity of Algorithm X" and give you the code (you must first write the recurrence yourself, then solve it). Practice recognizing code patterns as recurrences — see the Code-Pattern Cookbook on the Algorithms Analysis (2016) page.

Two Families of Recurrences

Exam angle: identify which family you have before picking a method. This one classification move tells you which method even applies (Master Theorem only works on the divide-and-conquer shape) and roughly what answer to expect, so you can sanity-check your final algebra against it.

---

Method 1 — Substitution (Iteration) Method

Expand the recurrence into itself repeatedly until a pattern in the substitution count k emerges, then find k from the base case and substitute back. Full 4-step method is on the Recursion page; summarized here:

1. Write the recurrence, expand the recursive term using the recurrence's own definition.
2. Spot the pattern after 2–3 substitutions, in terms of k.
3. Find k by setting the recursive argument equal to the base case.
4. Substitute k back, plug in the base value, simplify to a closed form.

Worked Example A — Subtractive: Factorial (summary)

$$T(n) = \begin{cases} 1 & n = 1 \\ n \cdot T(n-1) & n > 1 \end{cases}$$

Expanding: $T(n) = n(n-1)(n-2)\cdots(n-k+1)\cdot T(n-k)$. Base hits at $n-k=1 \implies k=n-1$, giving

$$T(n) = n(n-1)\cdots 2 \cdot 1 = n!$$

so $T(n) = \Theta(n!)$. Full step-by-step derivation: see Recursion.

Worked Example B — Subtractive with extra term: T(n) = T(n-1) + log n

$$T(n) = \begin{cases} 1 & n = 1 \\ T(n-1) + \log n & n > 1 \end{cases}$$

Step 1 — write the equation and substitute repeatedly:

$$\begin{aligned} T(n) &= T(n-1) + \log n \\ &= T(n-2) + \log(n-1) + \log n \\ &= T(n-3) + \log(n-2) + \log(n-1) + \log n \end{aligned}$$

Step 2 — spot the pattern after k substitutions:

General form:

$$T(n) = T(n-k) + \sum_{i=n-k+1}^{n} \log i$$

Step 3 — find k using the base case: recursion stops when the argument hits n = 1:

$$n - k = 1 \implies k = n-1$$

Step 4 — substitute k = n-1 back in:

$$T(n) = T(1) + \sum_{i=2}^{n} \log i$$

Since $T(1)=1$:

$$T(n) = 1 + \log(2 \cdot 3 \cdot 4 \cdots n) = 1 + \log(n!)$$

Step 5 — classify with Big-O using Stirling's approximation ($\log(n!) = \Theta(n\log n)$, a standard result worth memorizing on its own — it's how factorial's log connects back to the divide-and-conquer complexity class):

$$T(n) = 1 + \log(n!) = \Theta(n \log n)$$

Key reasoning point: this recurrence sits between the two families above — it subtracts like the factorial recurrence (k = n-1 substitutions, not log n of them), but because the added term $\log n$ shrinks in magnitude each step (unlike factorial's multiplied growing term), the sum of logs collapses to $\log(n!)$ rather than blowing up to $n!$ itself. Contrast all three: $T(n)=T(n-1)+O(1) \to O(n)$, $T(n)=T(n-1)+\log n \to O(n\log n)$, $T(n)=n\cdot T(n-1) \to \Theta(n!)$ — same subtractive shrinkage, three very different answers, purely from what's added/multiplied at each step.

Exam angle: FPSC sometimes disguises this exact pattern as "find the number of comparisons if a function does O(log n) work at every one of its n recursive subtractive calls" — recognize it as $T(n) = T(n-1) + \log n$ and the substitution method above applies directly.

Worked Example C — Divide-and-conquer: Binary Search (summary)

$T(n) = 4 + T(n/2)$, $T(1) = 2$ — substituting k times gives $T(n) = 4k + T(n/2^k)$; base hits at $n/2^k=1 \implies k=\log_2 n$, giving

$$T(n) = 4\log_2 n + 2 = O(\log n)$$

Full 9-step derivation (an actual 2016 FPSC Q5(b) past question): see Recursion.

---

Method 2 — Recursion Tree Method

Draw the recursion as a tree: each node is the non-recursive work done at that call (excluding its children); sum the work level by level, then sum across all levels.

1. Draw the root = the non-recursive cost of the top-level call, $f(n)$.
2. Expand each child the same way, one level per recursive call.
3. Find the total cost per level (often constant across levels) and the tree's depth (levels until reaching the base case) or number of leaves.
4. Sum level-costs × number-of-levels (or leaf-cost × number-of-leaves, plus internal levels) to get total $T(n)$.

Worked Example — Merge Sort: T(n) = 2T(n/2) + cn

Every level costs $cn$, independent of the level — a direct consequence of the work splitting into exactly half-sized pieces while doubling in count each time. The tree has $\log_2 n + 1$ levels (root at level 0, leaves at level $\log_2 n$, since the array halves from n down to 1).

Total:

$$T(n) = cn(\log_2 n + 1) = O(n \log n)$$

— matches the well-known Merge Sort complexity, derived here from first principles rather than quoted.

Exam angle: the recursion tree method is FPSC's preferred way to ask you to derive $O(n\log n)$ for Merge Sort rather than just state it — draw the tree, label each level's total cost, and explicitly state that it's constant ($cn$) across all $\log_2 n + 1$ levels; that constancy is the key insight examiners look for.

---

Method 3 — Master Theorem

For recurrences of the exact divide-and-conquer shape $T(n) = a\cdot T(n/b) + f(n)$ ($a \geq 1$ subproblems, each of size $n/b$, $b > 1$, plus $f(n)$ extra work), compare $f(n)$ against $n^{\log_b a}$:

Applying it

When the Master Theorem Does NOT Apply

• Unequal-sized subproblems, e.g. $T(n) = T(n/3) + T(2n/3) + n$ — needs a recursion tree instead (subproblem sizes differ, so there's no single b).
• f(n) not polynomially comparable to $n^{\log_b a}$, e.g. $T(n) = 2T(n/2) + n/\log n$ — f(n) is asymptotically between the cases (falls in the gap), so none of the 3 cases fit — needs the more general Akra–Bazzi method or a recursion tree.
• a not constant / a < 1, or subtractive recurrences like $T(n) = T(n-1) + n$ (this isn't of the $T(n/b)$ shape at all — use substitution instead, as in Example B).

Exam angle: a favorite FPSC MCQ trap is giving a recurrence resembling $T(n)=2T(n/2)+n/\log n$ and asking "which Master Theorem case applies?" — correct answer: none; Master Theorem is inapplicable here. Always check the polynomial-gap condition, not just "is f(n) bigger or smaller."

For the full deep-dive — recursion-tree intuition for why the theorem works, the generalized Case 2 (with an extra log factor), more worked examples per case, the regularity-condition check done explicitly, a decision flowchart, and dedicated CSS/FPSC practice questions — see the standalone Master Theorem page.

---

Method 4 — Characteristic Equation (Linear Homogeneous Recurrences)

For a recurrence that's a linear combination of previous terms with constant coefficients and no extra f(n) — the classic case being Fibonacci — solve algebraically instead of expanding:

Worked Example — Fibonacci: T(n) = T(n-1) + T(n-2)

1. Assume a solution of the form $T(n) = x^n$.
2. Substitute and divide out the smallest power:

$$x^n = x^{n-1} + x^{n-2} \quad\Longrightarrow\quad x^2 = x + 1$$

(the characteristic equation).

1. Solve the quadratic:

$$x^2 - x - 1 = 0 \quad\Longrightarrow\quad x = \frac{1 \pm \sqrt5}{2}$$

giving two roots: $\varphi \approx 1.618$ (the golden ratio) and $\psi \approx -0.618$.

1. General solution: $T(n) = A\varphi^n + B\psi^n$, with A, B fixed by the base cases ($T(0), T(1)$).
2. Since $|\psi| < 1$, the $B\psi^n$ term shrinks to 0 as n grows, so the dominant term is $\varphi^n$:

$$T(n) = \Theta(\varphi^n)$$

— commonly loosely quoted/bounded as $O(2^n)$ since $\varphi < 2$, which is the number normally expected in an FPSC answer unless the question specifically asks for the tight golden-ratio bound.

Cross-check against the recursion-tree/counting view: the naive recursive Fibonacci call tree is a binary tree of depth n where each node spawns 2 children — a direct match to the $O(2^n)$ upper bound; the characteristic-equation method gives the tighter $\Theta(\varphi^n)$ because not every branch of that tree actually runs to full depth. Full pseudocode + call-count reasoning: see Recursion.

Exam angle: FPSC rarely asks you to derive the characteristic equation from scratch, but frequently asks "why is naive recursive Fibonacci exponential?" — the expected answer combines both views: (a) the call tree branches in 2 directions at every non-base call, and (b) many identical subproblems (e.g. Fibonacci(n-3)) are recomputed across different branches instead of cached — the fix being memoization/DP, bringing it down to O(n).

---

Quick Reference — Common Recurrences → Answers

---

📌 Most Frequently Tested Pattern — Recurrence Relations (CSS/FPSC)

Across the Section-B papers reviewed for this workspace, recurrence-relation questions consistently follow one of two verified formats:

1. "Solve this recurrence using the substitution/iteration method" with either a subtraction-based (factorial-style) or division-based (Binary Search-style) recurrence given explicitly — see the confirmed real past question below.
2. A complexity-classification MCQ embedded inside a broader Recursion/Algorithms Analysis MCQ set (base case, what prevents infinite recursion, which notation is used, etc.) — see the MCQ examples on the Recursion and 🔥 Most Repeated — Algorithms & Data Structures pages.

✅ Verified Past Question

2016, Paper I, Q5(b) (6 marks) — Find the time complexity of Binary Search by resolving the recurrence $T(1)=2$ ($n\leq1$), $T(n)=4+T(n/2)$ ($n>1$), using the iterative substitution method.

Full 9-step solution: worked as Example C above, and in full detail on the Recursion page. Answer: $O(\log n)$.

📝 Practice Questions (in the same tested pattern — work these using the methods above)

These are not sourced from a specific verified past paper — they're modeled on the confirmed pattern above, for drilling all four methods.

1. Substitution, subtractive-with-term (Example B pattern): Solve $T(n) = T(n-1) + n$ for $n > 1$, $T(1) = 1$, using the substitution method. (Answer: $T(n) = \frac{n(n+1)}{2} = O(n^2)$ — same subtractive shrinkage as Example B, but a linearly-growing added term instead of a logarithmically-growing one.)
2. Recursion tree: Draw the recursion tree for $T(n) = 3T(n/2) + n$ and find $T(n)$. (This is Master Theorem Case 1: $a=3, b=2, f(n)=n$, $n^{\log_2 3} \approx n^{1.585}$ dominates → $\Theta(n^{\log_2 3})$.)
3. Master Theorem classification MCQ: Which case of the Master Theorem applies to $T(n) = 4T(n/2) + n$? ($a=4, b=2 \implies n^{\log_2 4} = n^2$; $f(n)=n=O(n^{2-\varepsilon})$ → Case 1 → $\Theta(n^2)$.)
4. Conceptual/short-answer: Explain why the Master Theorem cannot be applied directly to $T(n) = T(n/3) + T(2n/3) + n$. (Unequal subproblem sizes — no single b — use a recursion tree; the tree remains unbalanced but still resolves to $O(n\log n)$ since every level still totals n.)
5. Characteristic equation: Derive the closed-form growth rate of $T(n) = T(n-1) + T(n-2)$ and state why it is exponential rather than polynomial. (See Method 4 — $\Theta(\varphi^n)$.)
6. "Which method would you use" (identification MCQ): A recurrence of the form $T(n) = 8T(n/2) + n^2$ is best solved using: A) Master Theorem B) Characteristic equation C) Recursion tree only D) Cannot be solved. (Answer: A — it's exactly the $aT(n/b)+f(n)$ shape the theorem targets, though a recursion tree would confirm the same $\Theta(n^3)$ answer.)

Exam angle — the single highest-leverage move: before writing any algebra, classify the recurrence into one of the three families in the table near the top of this page. That one step tells the examiner (and you) which method you're about to apply and why — FPSC awards method-selection reasoning marks separately from the final closed-form answer.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2016 · Paper-I · Q5(b) · 6 marks

Q. Find the time complexity of binary search by solving the recurrence T(1) = 2 and T(n) = 4 + T(n/2) for n > 1, by iterative substitution.

Ans.

• T(n) = 4 + T(n/2)
• = 4 + 4 + T(n/4) = 2·4 + T(n/2²)
• = 3·4 + T(n/2³)
• After k steps: T(n) = 4k + T(n/2ᵏ).
• Stop when n/2ᵏ = 1, that is k = log₂ n.
• T(n) = 4 log₂ n + T(1) = 4 log₂ n + 2.
• Therefore T(n) = O(log n).