What is a Recurrence Relation in Algorithm Analysis?
Learn what a recurrence relation is, how to solve it with recursion trees or the Master Theorem, and how to explain it in interviews.
Expected Interview Answer
A recurrence relation expresses the running time of a recursive algorithm as a function of its running time on smaller inputs, such as T(n) = 2T(n/2) + O(n) for merge sort, and solving it (by substitution, recursion tree, or the Master Theorem) gives the algorithm's closed-form time complexity.
Every recursive algorithm splits work into subproblems and combines their results, and the recurrence captures exactly that shape: how many subproblems, how much smaller each one is, and how much non-recursive work happens outside the recursive calls. A recursion tree makes the total cost visible by summing the work done at every level of recursion down to the base case. The Master Theorem is a shortcut that classifies T(n) = aT(n/b) + f(n) into one of three cases by comparing f(n) against n^(log_b a), skipping the need to expand the whole tree by hand. Getting the recurrence wrong — miscounting subproblems or the split factor — is the single most common source of an incorrect Big-O answer for recursive code.
- Turns recursive code into an exact time-complexity formula
- Recursion trees make hidden per-level costs visible
- Master Theorem gives instant answers for common shapes
- Explains why some divide-and-conquer algorithms beat brute force
AI Mentor Explanation
A net-practice drill has a head coach splitting a squad of n players into two smaller groups of n/2 to be coached by assistants, and each assistant recurses the same split down to individual one-on-one sessions. The recurrence T(n) = 2T(n/2) + O(n) captures this: two half-size sub-drills plus O(n) minutes the head coach spends briefing the whole squad before splitting. Drawing a recursion tree of squad sizes level by level shows every level costs O(n) total briefing time, and there are O(log n) levels until groups shrink to one player, giving O(n log n) overall. This is exactly why a merge-sort-style squad-splitting drill finishes faster than coaching every player one at a time from a single list.
Step-by-Step Explanation
Step 1
Write the recurrence from the code
Count the number of recursive calls (a), how much smaller each subproblem is (n/b), and the non-recursive work (f(n)).
Step 2
Draw the recursion tree
Expand levels until the subproblem size hits the base case, tracking the total work done at each level.
Step 3
Sum the levels
Add the per-level costs across all O(log n) levels (for the common a, b splits) to get the total.
Step 4
Or apply the Master Theorem
Compare f(n) to n^(log_b a) to classify into one of three cases without expanding the full tree.
What Interviewer Expects
- Correctly translate recursive code into a recurrence T(n) = aT(n/b) + f(n)
- Explain the recursion-tree method by summing per-level costs
- State the Master Theorem's three cases at a high level and when it applies
- Give a concrete example, such as merge sort's T(n) = 2T(n/2) + O(n) resolving to O(n log n)
Common Mistakes
- Miscounting the number of recursive calls or the split factor
- Forgetting the non-recursive combine cost f(n) entirely
- Applying the Master Theorem when f(n) does not fit its polynomial comparison requirements
- Assuming every divide-and-conquer recurrence resolves to O(n log n) without checking
Best Answer (HR Friendly)
“A recurrence relation is basically a formula for how long a recursive algorithm takes, written in terms of how long it takes on smaller pieces of the same problem. I solve it either by drawing out a tree of all the recursive calls and adding up the work at each level, or by using the Master Theorem as a shortcut for common patterns like merge sort.”
Code Example
def merge_sort(arr):
# Base case: T(1) = O(1)
if len(arr) <= 1:
return arr
mid = len(arr) // 2
# Two recursive calls on n/2 each -> 2T(n/2)
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# Combine step scans both halves once -> O(n)
return merge(left, right)
def merge(left, right):
result, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
return result + left[i:] + right[j:]
# Recurrence: T(n) = 2T(n/2) + O(n)
# Master Theorem case 2 (f(n) = Theta(n^log_b(a))) -> T(n) = O(n log n)Follow-up Questions
- How would you solve T(n) = T(n-1) + O(1) versus T(n) = T(n/2) + O(1)?
- What are the three cases of the Master Theorem and what distinguishes them?
- How would you write the recurrence for binary search?
- When does the Master Theorem fail to apply, and what would you use instead?
MCQ Practice
1. What is the closed-form solution to the recurrence T(n) = 2T(n/2) + O(n)?
This matches Master Theorem case 2, where f(n) = Theta(n^log_b a), giving O(n log n), the classic merge sort result.
2. In the recurrence T(n) = aT(n/b) + f(n), what does the parameter “a” represent?
"a" is the number of recursive calls made at each level; "b" is the factor by which the input shrinks.
3. A recursion tree for T(n) = 2T(n/2) + O(n) has how many levels before reaching the base case?
Each level halves the input size, so it takes O(log n) levels to shrink n down to the base case of size 1.
Flash Cards
What does a recurrence relation describe? — The running time of a recursive algorithm in terms of its running time on smaller subproblems.
What is the general form of a divide-and-conquer recurrence? — T(n) = aT(n/b) + f(n), where a is the number of subproblems, b is the shrink factor, and f(n) is the combine cost.
What two methods solve a recurrence relation? — Expanding a recursion tree and summing per-level costs, or applying the Master Theorem directly.
What recurrence describes merge sort, and what is its solution? — T(n) = 2T(n/2) + O(n), which solves to O(n log n).