Analyzing Recursive Algorithms with Recurrence Relations and the Master Theorem

In our last two lessons, we built a solid foundation for analyzing algorithm efficiency. We started with time complexity and Big-O notation, then explored space complexity, including the memory used by the recursion call stack. You learned to reason about the performance of recursive functions like factorial and Fibonacci, but our analysis was still somewhat informal.

Today, we will formalize the process of analyzing the time complexity of recursive algorithms. This lesson introduces two powerful mathematical tools that are indispensable for technical interviews: recurrence relations and the Master Theorem. You will learn how to translate a recursive piece of code into a mathematical equation (a recurrence relation) and then use a "cheat code" (the Master Theorem) to solve many of these equations almost instantly. This skill allows you to move beyond guessing and prove the complexity of your recursive solutions.

Part 1: Formulating Recurrence Relations

In the previous lessons, we concluded that the time complexity of factorial(n) was $O (n)$ and the naive fib(n) was $O (2^{n})$ . But how do we arrive at these conclusions rigorously? The first step is to create a recurrence relation.

A recurrence relation is simply an equation that defines a function in terms of itself with smaller inputs. For an algorithm, it defines the time to solve a problem of size n, or $T (n)$ , based on the time it takes to solve smaller subproblems.

A recurrence relation has two essential components derived directly from the code:

The Recursive Case: Describes the cost of breaking the problem down, making recursive calls to subproblems, and combining the results.
The Base Case: Describes the cost of solving the smallest version of the problem, where recursion stops. This is usually a constant time operation, $O (1)$ .

Let's see how this works.

Writing Recurrence Relations

This video from Neso Academy provides an excellent, clear introduction to the concept of recurrence relations and walks through the process of creating one for the factorial algorithm.

Watch the introduction to understand the role of recurrence relations in analysis: Steps to Analyze. Pay attention to the definition of a recurrence relation: What is a Recurrence Relation?. The most important part is the step-by-step derivation for the factorial function. Follow how the if and else blocks of the code are translated into the mathematical T(n) notation: Writing for Factorial.

As the video demonstrated for factorial, the recurrence relation is:

$T (n) = T (n - 1) + c$ (or $O (1)$ )
$T (1) = c$

This perfectly models the algorithm: to compute factorial(n), you do one recursive call on a problem of size n-1 and a constant amount of extra work (the multiplication).

Recursive algorithms follow several common patterns. Understanding these patterns helps you write recurrence relations quickly.

Analysis of Recursion in Data Structures and Algorithms

This article from EnjoyAlgorithms provides a great overview of formulating recurrence relations for various common recursive patterns.

First, read the introduction to understand the general formula for a recurrence relation: T(n) = .... Then, review the examples provided for different patterns. This will be invaluable for your problem-solving toolkit: Decrease by a constant factor (like Binary Search): Binary Search. Here, the problem size is halved at each step. Dividing into two equal subproblems (like Merge Sort): Merge Sort. Here, you make two recursive calls on problems half the size and do linear work to combine them. Dependent subproblems (like Fibonacci): Fibonacci. Here, the calls are on n-1 and n-2. Finally, internalize the three-step process for analysis: identify subproblems, write the recurrence, and solve it.

By now, you should be comfortable with the first two steps: identifying subproblems and writing the recurrence. The next step is solving them. For simple relations like $T (n) = T (n - 1) + c$ , you can expand it:
$T (n) = (T (n - 2) + c) + c = T (n - 2) + 2 c = ... = T (1) + (n - 1) c = O (n)$ .

But for more complex relations like $T (n) = 2 T (n /2) + n$ , this "substitution method" becomes tedious. This is where the Master Theorem comes in.

Part 2: Solving Recurrence Relations with the Master Theorem

The Master Theorem is a "cookbook" method for solving recurrence relations that follow a specific form, typical of divide and conquer algorithms. It saves you from the manual work of substitution or drawing recursion trees.

The theorem applies to recurrences of the form:
$T (n) = a T (n / b) + f (n)$
where:

n is the size of the problem.
a is the number of subproblems in the recursion (a >= 1).
n/b is the size of each subproblem (b > 1).
f(n) is the cost of the work done outside the recursive calls (dividing the problem and combining the results). For the simplified version of the theorem we'll use, we'll represent this as $O (n^{k})$ .

The theorem compares the work done at the root of the recursion tree ( $f (n)$ ) with the work done at the leaves ( $O (n^{l o g_{b} a})$ ). It essentially asks: "What is the dominant part of the work? The initial split/combine, or the explosion of work from all the recursive calls?"

There are three cases.

Analysis of Recursion in Data Structures and Algorithms

Continuing with the same article, let's now focus on the Master Theorem.

Read the section introducing the Master Theorem. Focus on understanding the format T(n) = aT(n/b) + O(n^k). Next, study the three cases of the theorem carefully. This is the core of the method: Case 1 (Leaf-heavy) Case 2 (Balanced) Case 3 (Root-heavy) Finally, walk through the examples provided to see how these cases are applied to real algorithms like Binary Search and Merge Sort. This will solidify your understanding of how to find a, b, and k and choose the correct case. Read through all four examples.

Let's summarize the logic:

Identify a, b, and k from the recurrence $T (n) = a T (n / b) + O (n^{k})$ .
Calculate $lo g_{b} a$ .
Compare $k$ with $lo g_{b} a$ and apply the corresponding case:
- Case 1: $lo g_{b} a > k$ . The cost is dominated by the number of leaves. The complexity is $O (n^{l o g_{b} a})$ .
- Case 2: $lo g_{b} a = k$ . The work is evenly distributed across the levels of the recursion tree. The complexity is $O (n^{k} lo g n)$ .
- Case 3: $lo g_{b} a < k$ . The cost is dominated by the work done at the root. The complexity is $O (n^{k})$ .

Practice Problems

To master this, you need practice. The following resource provides a set of solved problems. It uses a slightly more general form of the theorem, but the logic for finding a, b, and k is the same.

Master Theorem | Master Theorem Examples | Gate Vidyalay

This article from Gate Vidyalay is an excellent resource for practice. It presents the theorem and then jumps straight into worked-out problems.

First, quickly review the three cases. Note that their comparison is a vs b^k, which is equivalent to log_b(a) vs k. Also, they include a p term for logarithmic factors in f(n), but for most problems we'll see, p=0. Now, work through these problems step-by-step, trying to solve them yourself before reading the solution: Problem 1: T(n) = 3T(n/2) + n^2. This is a classic Case 3 example. Problem 2: T(n) = 2T(n/2) + n log n. A Case 2 example with a logarithmic factor. Problem 4: T(n) = sqrt(2)T(n/2) + log n. A Case 1 example. Problem 6: T(n) = 3T(n/3) + n/2. This one shows that constant factors in f(n) are ignored.

Important Note: The Master Theorem is a powerful shortcut, but it doesn't solve all recurrence relations. It doesn't apply to relations like Fibonacci's ( $T (n) = T (n - 1) + T (n - 2) + c$ ) where the subproblem size is not a division (n-c instead of n/b), or when f(n) is not polynomial. For those, other methods like substitution or recursion trees are needed.

Key Takeaways

Recurrence Relations are mathematical equations that model the time complexity of a recursive algorithm by expressing $T (n)$ in terms of its subproblems.
Formulating a recurrence relation involves identifying the base case (usually $O (1)$ ) and the recursive case.
The Master Theorem is a powerful technique to solve divide-and-conquer recurrence relations of the form $T (n) = a T (n / b) + O (n^{k})$ .
The theorem's three cases depend on the comparison between $lo g_{b} a$ (representing the growth rate of subproblems) and $k$ (representing the growth rate of work per step).
- Leaf-dominated ( $lo g_{b} a > k$ ): $O (n^{l o g_{b} a})$
- Balanced ( $lo g_{b} a = k$ ): $O (n^{k} lo g n)$
- Root-dominated ( $lo g_{b} a < k$ ): $O (n^{k})$

Conclusion

You have now added a crucial theoretical tool to your arsenal. The ability to quickly formulate and solve recurrence relations will allow you to confidently analyze the efficiency of complex algorithms like Merge Sort, Quick Sort, and many tree-based algorithms we will encounter later.

In the next lesson, we will shift our focus from this high-level analysis back to the code itself. You will learn to trace the execution of a recursive function on the call stack, a practical skill essential for debugging and fully understanding how recursion works under the hood.

Recommended resources

Part 1: Formulating Recurrence Relations

Part 2: Solving Recurrence Relations with the Master Theorem

Practice Problems

Key Takeaways

Conclusion