Analyzing Recursive Algorithms with Recurrence Relations

1. From Recursive Code to a Recurrence Relation

A recurrence relation is an equation that defines a function's value in terms of its value on smaller inputs. This is a natural fit for analyzing recursive algorithms. To write one, we need to identify two key components from the code:

1. Recursive Calls: How many recursive calls are made, and how much smaller is the input for each call?
2. Work at Each Step: How much work is done in the function outside of the recursive calls? (e.g., comparisons, arithmetic, creating data structures).

Let's see how this works in practice.

As you saw, a recursive algorithm's structure dictates the form of its recurrence relation.

• Linear Recursion: An algorithm like times1 that calls itself once with a slightly smaller input (e.g., n-1) yields a recurrence like T(n) = T(n-1) + O(1).
• Divide and Conquer: An algorithm like times2 or Merge Sort, which divides the problem into subproblems (e.g., n/2), yields recurrences like T(n) = aT(n/b) + f(n), where a is the number of subproblems, b is the factor by which the input size is reduced, and f(n) is the work done at each step.

Now that we can formulate these relations, how do we solve them to get a Big-O bound?

2. The Recursion Tree Method: Building Intuition

The recursion tree method is a visual and intuitive way to analyze the total work done by a recursive algorithm. It's particularly useful for building a hypothesis about the time complexity, which you can then prove formally.

The process involves four steps:

1. Draw a tree representing the recursive calls. The root is the initial call, and its children are the subproblems it calls, and so on.
2. Label each node with the cost (work done) at that specific step, excluding the cost of its children's recursive calls.
3. Sum the costs for each level of the tree.
4. Sum the costs of all levels to get the total runtime.

This video provides a clear, step-by-step demonstration.

The example in the video, T(n) = 2T(n/2) + 4n, is characteristic of algorithms like Merge Sort. The work at each level was constant (4n). Let's look at another example where the work per level forms a geometric series.

For this tree:

• Level 0: Cost is cn^2.
• Level 1: There are 3 nodes, each with cost c(n/4)^2. Total cost: 3 * c(n^2/16) = (3/16)cn^2.
• Level 2: There are 3^2=9 nodes, each with cost c(n/4^2)^2. Total cost: 9 * c(n^2/256) = (9/256)cn^2 = (3/16)^2 cn^2.
• Total Cost: The sum is a geometric series cn^2 * (1 + 3/16 + (3/16)^2 + ...) which is dominated by the first term. The entire sum is bounded by a constant factor of the root's cost, so the complexity is O(n^2).

The recursion tree gives us a strong intuitive guess. But for a formal interview setting, especially at the Principal level, being able to prove your guess is a significant differentiator.

3. The Substitution Method: A Formal Proof

The substitution method is how we formally prove that our guessed complexity is correct. It uses mathematical induction, which aligns perfectly with your preference for understanding proofs of correctness.

The process:

1. Guess the solution (e.g., using the recursion tree method, or just from experience). Let's say we guess O(g(n)).
2. Prove the guess by induction. We need to show that T(n) ≤ c * g(n) for some constant c > 0 and for all n ≥ n_0.
   • Inductive Hypothesis: Assume that the bound T(k) ≤ c * g(k) holds for all k < n.
   • Inductive Step: Substitute the recurrence relation into the inequality and use the inductive hypothesis to prove that the bound holds for n.

This is a method that demands precision. A small mistake can invalidate the entire proof.

4. Advanced Technique: Change of Variables

Occasionally, you may encounter a recurrence that doesn't fit a standard pattern. A powerful technique for a Principal-level toolkit is the change of variables, which can transform a strange recurrence into a familiar one.

Consider T(n) = 2T(√n) + log n. The √n term is unusual.
Let's introduce a new variable, m = log₂n. This means n = 2^m, and √n = (2^m)^(1/2) = 2^(m/2).
If we substitute T(n) = T(2^m) with a new function S(m), we get:
S(m) = T(2^m) = 2T(2^(m/2)) + m = 2S(m/2) + m.

This is the exact recurrence for Merge Sort! We know its solution is S(m) = O(m log m). Now we just substitute back:
T(n) = S(m) = O(m log m) = O(log n * log(log n)).

Conclusion

You now have a robust framework for analyzing the runtime of recursive algorithms from first principles.

Key Takeaways:

• Recurrence Relations: They are the mathematical model of a recursive algorithm's runtime, defined by the number of subproblems, the reduction in input size, and the work done at each step.
• Recursion Tree Method: A fantastic visual tool for building an intuition and forming a hypothesis about an algorithm's complexity. Summing the work at each level is the key.
• Substitution Method: The formal, proof-based technique to verify your hypothesis. It requires mathematical rigor—you must prove your guess holds in its exact form, not just a looser Big-O bound.
• Technique Synergy: These methods work together. Use the recursion tree to guess, and the substitution method to prove.

Next Lesson Preview:
You may have noticed that many divide-and-conquer algorithms result in recurrences of the form T(n) = aT(n/b) + f(n). While you can solve these from scratch every time, there is a powerful shortcut. In our next lesson, we will explore the Master Theorem, a "cookbook" recipe for solving this common class of recurrences instantly.