Solving Recurrence Relations

40 mins

Master the mathematical techniques to calculate the time complexity of recursive algorithms. This section covers the Substitution Method, Recursion Tree Method, and the highly-tested Master's Theorem.

Learning Goals

Understand what a recurrence relation is and why it's necessary for recursive algorithms.
Memorize the three cases of the Master's Theorem and identify when it fails.
Trace mathematical solutions using the Substitution Method for linear recurrences.
Visualize how recursive function calls split work using the Recursion Tree Method.

The Basics of Recurrence

While calculating the time complexity of a standard for loop is straightforward, analyzing a recursive algorithm (an algorithm that calls itself, like Merge Sort or Binary Search) is mathematically complex. We cannot simply count loops. Instead, we must define the running time as a mathematical equation called a Recurrence Relation.

A recurrence relation defines a sequence based on its previous terms. For example, the time $T(n)$ to sort an array of size $n$ might be defined as the time to sort two halves $T(n/2)$ plus the time to merge them $O(n)$ . $T(n) = 2T(n/2) + O(n)$

There are three primary methods to solve these recurrences and find the asymptotic bound:

The Substitution Method: Expanding the equation mathematically to guess and prove the bound.
The Recursion Tree Method: Visualizing the recursive calls as a tree and summing the work done at each level.
The Master's Theorem: A direct, formulaic shortcut for solving divide-and-conquer recurrences.

The Master's Theorem (The Shortcut)

The Master's Theorem provides a "cookbook" method for solving recurrences of the specific form: $T(n) = aT(n/b) + f(n)$

Where:

$a \ge 1$ : The number of recursive subproblems.
$b > 1$ : The factor by which the input size is divided.
$f(n)$ : The cost of the work done outside the recursive calls (like merging or partitioning).

To solve, you always calculate the critical exponent: $n^{\log_b a}$ , and compare it to $f(n)$ .

The 3 Cases:

Case 1 (Heavy Leaves): If $f(n) = O(n^{\log_b a - \epsilon})$ for some constant $\epsilon > 0$ . Meaning: The work at the leaves dominates. Solution: $T(n) = \Theta(n^{\log_b a})$
Case 2 (Balanced Work): If $f(n) = \Theta(n^{\log_b a})$ . Meaning: The work is evenly distributed across the tree levels. Solution: $T(n) = \Theta(n^{\log_b a} \log n)$
Case 3 (Heavy Root): If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some constant $\epsilon > 0$ . Meaning: The work at the root (the $f(n)$ term) completely dominates. Regularity Condition: You must also prove $a f(n/b) \le c f(n)$ for $c < 1$ . Solution: $T(n) = \Theta(f(n))$

Trace: Master's Theorem Application

1
Step 1
Given the recurrence $T(n) = 3T(n/2) + n^2$ . We identify the constants: $a = 3$ , $b = 2$ , and the function $f(n) = n^2$ .
2
Step 2
We calculate $n^{\log_b a}$ , which is $n^{\log_2 3}$ . Since $\log_2 3 \approx 1.58$ , our critical exponent is $n^{1.58}$ .
3
Step 3
We compare $f(n) = n^2$ with our critical exponent $n^{1.58}$ . Since $n^2$ grows polynomially faster than $n^{1.58}$ (specifically, $n^2 = \Omega(n^{1.58 + 0.4})$ ), Case 3 applies. The work at the root dominates.
4
Step 4
For Case 3, we MUST check if $a f(n/b) \le c f(n)$ . Substituting our values: $3(n/2)^2 \le c n^2 \implies \frac{3}{4}n^2 \le c n^2$ . This holds true for any constant $c \ge 3/4$ . The condition is satisfied.
5
Step 5
By Master's Theorem Case 3, the time complexity is strictly determined by $f(n)$ . Therefore, $T(n) = \Theta(n^2)$ .

Trace: The Substitution Method

1
Step 1
Given $T(n) = T(n-1) + n$ with a base case of $T(1) = 1$ . Let's expand $T(n-1)$ to see the pattern: $T(n-1) = T(n-2) + (n-1)$ .
2
Step 2
Substitute the expansion back into the original equation: $T(n) = [T(n-2) + (n-1)] + n$ . Let's expand one more time for clarity: $T(n-2) = T(n-3) + (n-2)$ . So, $T(n) = T(n-3) + (n-2) + (n-1) + n$ .
3
Step 3
We can clearly see a pattern emerging. After $k$ expansions, the equation looks like this: $T(n) = T(n-k) + (n-(k-1)) + \dots + (n-1) + n$ .
4
Step 4
The recursion stops when we hit the base case $T(1)$ . This happens when $n - k = 1$ , which means $k = n - 1$ . Substitute $k = n - 1$ into our generalized equation: $T(n) = T(1) + 2 + 3 + \dots + (n-1) + n$ .
5
Step 5
Since $T(1) = 1$ , the equation becomes the sum of the first $n$ natural numbers: $1 + 2 + 3 + \dots + n$ . The mathematical formula for this arithmetic progression is $\frac{n(n+1)}{2}$ . Expanding this gives $\frac{n^2}{2} + \frac{n}{2}$ . Dropping constants yields $O(n^2)$ .

The Recursion Tree Method

While the Substitution Method relies heavily on algebra, the Recursion Tree Method relies on visualization. It converts the recurrence into a tree where:

Each node represents the cost of a single subproblem.
The tree branches represent the recursive calls.

To find the total complexity, you sum the costs across all nodes at each depth to get a set of per-level costs, and then sum those per-level costs across the entire depth of the tree.

Example Visualization for $T(n) = 2T(n/2) + n$ (Merge Sort):

Level 0 Cost: 1 node $\times \ n$ = $n$
Level 1 Cost: 2 nodes $\times \ n/2$ = $n$
Level 2 Cost: 4 nodes $\times \ n/4$ = $n$

At every single level, the total work done is $n$ . How deep does the tree go before hitting size 1? The depth of a tree that halves at each step is $\log_2 n$ . Therefore, Total Cost = (Cost per level) $\times$ (Number of levels) = $n \times \log_2 n \implies O(n \log n)$ .

Knowledge Check

Question 1 of 3

Q1Single choice

The recurrence T(n) = T(n/2) + 1 has a time complexity of:

O(n)

O(log n)

O(n log n)

O(n²)

Master's Theorem - Visual Guide

web

Complexity Analysis and Time-Space Trade-offs

Recurrence Relations and Recursive Algorithm Analysis