---
title: "Methods for solving recurrences"
subject: "Data Structure and Algorithm"
chapter: 9
key: "semester_4/data_structure_and_algorithm:recurrence-solving-methods"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/recurrence-solving-methods
site: BCT Engineering
---

# Methods for solving recurrences

Data Structure and Algorithm · Chapter 9: Growth Functions

- Asked in: 2071 Bhadra, 2 marks
- Video: [Recurrence Equations Overview (Computer Science/Algorithms)](https://www.youtube.com/watch?v=l0iXqhqfDPo) — Keith Galli
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/recurrence-solving-methods
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-9

## Question

Write three methods for solving recurrences.

## Short answer

Substitution method guesses and proves by induction; recursion-tree method draws the call tree and sums per-level costs; master theorem compares f(n) with n^(log_b a) to directly obtain the asymptotic bound.

## Answer

Three methods to solve a recurrence such as T(n) = 2T(n/2) + n:
1. **Substitution method:** guess the form of the solution (e.g. T(n) = O(n log n)) and prove it by mathematical induction.
2. **Recursion-tree method:** draw the tree of recursive calls, find the cost at each level, and sum over all levels. For the example, each level costs n and there are log n levels, giving Θ(n log n).
3. **Master theorem:** for T(n) = aT(n/b) + f(n), compare f(n) with n^(log_b a) to get the answer directly. Here a = 2, b = 2, f(n) = n = n^1, so T(n) = Θ(n log n).

(Iteration/back-substitution, expanding repeatedly, is another form of the first method.)

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is the substitution method?
   A. Guess the solution form and prove it by induction
   B. Draw a tree of calls
   C. Apply a fixed formula
   D. Run the program
   Answer: A. Guess then verify. (Key point: Substitution method)

2. For T(n) = 2T(n/2) + n, what is the cost per level and the number of levels?
   A. n^2 per level, 2 levels
   B. n per level, log n levels
   C. 1 per level, n levels
   D. 2n per level, n levels
   Answer: B. Total is Theta(n log n). (Key point: Recursion tree)

3. For T(n)=2T(n/2)+n, a=2, b=2. How is the answer found?
   A. f(n) is smaller, so T(n) = Theta(n)
   B. f(n) is larger, so T(n) = Theta(n^2)
   C. f(n) = n^(log_2 2) = n, so T(n) = Theta(n log n)
   D. It cannot be solved
   Answer: C. f(n) matches n^(log_b a), giving the extra log factor. (Key point: Master theorem)

## Related in other subjects

- [Three students solving a problem](https://www.bctengineer.com/question.md?key=semester_5%2Fprobability_and_statistics%3Athree-students-solve-problem) — Probability and Statistics, chapter 1