Foundations
Solving Recurrence Relations
Difficulty: Advanced
Writing the recurrence T(n) = 2 T(n/2) + n for merge sort is the easy part. Turning it into the closed-form O(n log n) is where the real algorithm analysis happens, and it is exactly what this lesson is for. Solving Recurrence Relations...
Solving Recurrence Relations
Writing the recurrence T(n) = 2 T(n/2) + n for merge sort is the easy part. Turning it into the closed-form O(n log n) is where the real algorithm analysis happens, and it is exactly what this lesson is for. Solving Recurrence Relations gives you a small toolkit that, used well, can analyze nearly every recursive algorithm you will meet in interviews, papers, or production.
This lesson walks through five methods. The Substitution Method has you guess the solution and prove it by induction, useful when you already suspect the bound. The Recursion Tree Method visualizes work level by level and sums it; this is how you see why merge sort spends n work per level over log_2(n) levels. The Master Theorem mechanically solves the divide-and-conquer form T(n) = a T(n/b) + f(n) via three cases, and you will memorize when each case fires. The Extended Master Theorem patches the gap when f(n) includes logarithmic factors. The Akra-Bazzi Method generalizes to unequal subproblem sizes that the basic theorem cannot handle. You will practice picking the right tool for each recurrence rather than blindly reaching for the same one every time.
This lesson directly continues Recurrence Relations, where you learned to write T(n) from recursive code, and reuses ideas from Big-O Notation (Upper Bound) and Mathematical Sequences for the underlying summation arguments.
With the analysis sub-track complete, you will pivot back to advanced math in Modular Arithmetic, where number-theoretic tools meet algorithm design.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Apply the Substitution Method by guessing a solution and proving it correct using mathematical induction.
Draw and analyze a recursion tree to compute total work by summing costs across all levels.
State the three cases of the Master Theorem and apply them to solve T(n) = aT(n/b) + f(n).
Identify when the Master Theorem does not apply and use the Extended Master Theorem for logarithmic factors.
Apply the Akra-Bazzi method to recurrences with unequal subproblem sizes.
Choose the most efficient solving method for a given recurrence.
Why This Matters
01
Writing a recurrence from code is only half the job -- you must solve it to get the actual Big-O bound. This lesson completes the analysis pipeline from recursive code to closed-form complexity.
02
The Master Theorem alone covers the vast majority of divide-and-conquer recurrences you will encounter in interviews and competitive programming, making it an essential tool in your toolkit.
03
Understanding the recursion tree method builds deep intuition about why algorithms like merge sort are O(n log n) -- you can literally see the work distribution across recursion levels.
04
Advanced methods like Akra-Bazzi let you analyze sophisticated algorithms with unequal subproblem sizes that defeat the basic Master Theorem.
Key Terms
8 terms you'll encounter in this lesson
Substitution Method
A technique for solving recurrences by guessing the closed-form solution and then proving it correct using mathematical induction. The challenge lies in making a good guess.
Recursion Tree Method
A visual approach that expands the recurrence into a tree, computes the work done at each level, and sums all levels to find the total cost. It provides strong intuition but is not always considered a formal proof by itself.
Master Theorem
A formula that directly solves recurrences of the form T(n) = aT(n/b) + Theta(n^d) by comparing log_b(a) to d. It has three cases corresponding to leaf-heavy, balanced, and root-heavy recursion trees.
Critical Exponent (log_b a)
The value log_b(a) in the Master Theorem, where a is the number of subproblems and b is the factor by which the problem shrinks. It determines how fast the number of subproblems grows relative to how fast each shrinks.
Extended Master Theorem
An extension that handles recurrences where f(n) includes logarithmic factors, such as T(n) = 2T(n/2) + n log n. The basic Master Theorem's Case 2 becomes a family of sub-cases.
Akra-Bazzi Method
A generalization of the Master Theorem that handles recurrences with unequal subproblem sizes, like T(n) = T(n/3) + T(2n/3) + O(n). It finds a value p such that the sum of (a_i / b_i^p) = 1, then integrates.
Leaf-Heavy (Case 1)
When log_b(a) > d in the Master Theorem, meaning subproblems multiply faster than the work shrinks. The leaves dominate and T(n) = Theta(n^(log_b a)).
Root-Heavy (Case 3)
When log_b(a) < d in the Master Theorem, meaning the work at each level grows fast enough to dominate. The root level dominates and T(n) = Theta(f(n)).
Heads Up
Common misconceptions to watch out for
"The Master Theorem works for all recurrences"
The Master Theorem only applies to recurrences of the form T(n) = aT(n/b) + f(n) where a >= 1 and b > 1. It does not work for recurrences like T(n) = T(n-1) + O(1) (linear decrease), T(n) = T(n-1) + T(n-2) (multi-branch), or cases where f(n) falls in the gap between cases.
"In the recursion tree method, you only need to count the number of leaves"
You must sum the work at ALL levels, not just count the leaves. In some recurrences (Case 3 / root-heavy), the root level does the most work. In balanced cases (Case 2), every level contributes equally. Only in leaf-heavy cases (Case 1) does the leaf count determine the answer.
"If I cannot apply the Master Theorem, the recurrence is unsolvable"
The recursion tree method and substitution method work on any recurrence. The Akra-Bazzi method generalizes the Master Theorem significantly. There is almost always a way to solve a recurrence -- the Master Theorem is just the fastest shortcut when it applies.
"Case 2 of the Master Theorem always gives O(n log n)"
Case 2 gives T(n) = Theta(n^d * log n) where d = log_b(a). This is O(n log n) only when d = 1 (e.g., merge sort). If d = 0 (e.g., binary search), Case 2 gives O(log n). If d = 2, Case 2 gives O(n^2 log n).