Recurrence Relations, Recursion Trees, and the Master Theorem
Formulate mathematical recurrence relations for divide-and-conquer algorithms and solve them rigorously using recursion trees and the Master Theorem.
By the end, you’ll be able to…
- Formulate recurrence relations of the form T(n) = aT(n/b) + f(n) for recursive algorithms
- Apply the Master Theorem across its three fundamental cases with regularity condition checks
- Construct recursion trees to calculate exact per-level work and overall asymptotic bounds
01The Anatomy of Divide-and-Conquer Recurrences
To rigorously analyze recursive algorithms such as Merge Sort, Quick Sort, Binary Search, and Strassen's Matrix Multiplication, engineers must express their runtime as a recurrence relation: a mathematical equation that defines a function in terms of its value on smaller inputs.
The canonical form for divide-and-conquer recurrences is T(n) = a * T(n/b) + f(n), where 'a' represents the number of subproblems spawned at each recursive step, 'n/b' represents the reduced subproblem size, and 'f(n)' denotes the cost of dividing the problem and combining the subproblem results.
For example, in Merge Sort, an array of size n is divided into a = 2 subproblems, each of size n/b = n/2. The division cost is O(1) and the merging step takes linear work O(n). Hence, Merge Sort yields the famous recurrence: T(n) = 2T(n/2) + O(n).
02The Master Theorem: Three Critical Cases
The Master Theorem provides a cookbook solution for solving recurrences of the form T(n) = aT(n/b) + O(n^c). The outcome depends on a comparison between the work done at the leaves (n^(log_b a)) versus the work done at the root (f(n) = n^c):
Case 1 (Leaf Heavy): If log_b(a) > c, the work is dominated by the base-case leaf nodes. The total time complexity is T(n) = Theta(n^(log_b a)). Example: T(n) = 8T(n/2) + O(n^2). Here a=8, b=2, c=2. Since log_2(8) = 3 > 2, T(n) = Theta(n^3).
Case 2 (Balanced Work): If log_b(a) == c, work is distributed evenly across all levels of the recursion tree. The total time complexity is T(n) = Theta(n^c * log n). Example: Merge Sort has a=2, b=2, c=1. Since log_2(2) = 1 == 1, T(n) = Theta(n log n).
Case 3 (Root Heavy): If log_b(a) < c and the regularity condition holds (a * f(n/b) <= k * f(n) for k < 1), work at the root dominates. Total time complexity is T(n) = Theta(f(n)). Example: T(n) = 2T(n/2) + O(n^2). log_2(2) = 1 < 2, so T(n) = Theta(n^2).
+--------+---------------------+-------------------------------+-----------------------------------+| Case | Condition | Dominant Stage | Resulting Complexity |+--------+---------------------+-------------------------------+-----------------------------------+| Case 1 | log_b(a) > c | Leaves (Base cases) | Theta(n^(log_b a)) || Case 2 | log_b(a) == c | Uniform across all log n lvls | Theta(n^c * log n) || Case 3 | log_b(a) < c | Root (Divide/Combine) | Theta(f(n)) |+--------+---------------------+-------------------------------+-----------------------------------+03Recursion Tree Visualization and Level Sums
When a recurrence does not fit the Master Theorem cleanly—such as T(n) = T(n/3) + T(2n/3) + O(n)—the recursion tree method provides the most reliable analytical pathway. In this method, we draw a tree where each node represents the cost f(subproblem_size) at that specific recursive invocation.
Let us trace T(n) = T(n/3) + T(2n/3) + cn:
Level 0 (Root): cn work.
Level 1: c(n/3) + c(2n/3) = cn work.
Level 2: c(n/9) + c(2n/9) + c(2n/9) + c(4n/9) = cn work.
Every full level sums to exactly cn work! The shortest path to a leaf has depth log_3(n), while the longest path has depth log_(3/2)(n). Because every level does cn work and the tree depth is Theta(log n), the total running time bounded from above and below is Theta(n log n).
04Practical Pitfalls: When Master Theorem Fails
Engineers must recognize when the standard Master Theorem cannot be applied: First, when 'a' is not a constant (e.g., T(n) = n * T(n/2) + O(n)). Second, when 'b' is not constant (e.g., Fibonacci recurrence T(n) = T(n-1) + T(n-2) + O(1), which requires characteristic equation analysis).
Third, when the gap between f(n) and n^(log_b a) is not polynomial (e.g., T(n) = 2T(n/2) + n/log n). In such cases, the extended Akra-Bazzi method or substitution induction must be applied.
The ideas worth keeping.
- Recurrence relations capture divide-and-conquer costs: T(n) = aT(n/b) + f(n).
- The Master Theorem evaluates whether work is concentrated at the leaves (Case 1), root (Case 3), or balanced across levels (Case 2).
- When subproblems are non-uniform, use recursion trees to sum per-level work systematically.
Make it yours.
Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.
Exercise 1: Using the Master Theorem determine the tight
Using the Master Theorem, determine the tight asymptotic time complexity of T(n) = 4T(n/2) + O(n). Identify a, b, c and which case applies.
Explore a worked solution
// a = 4// b = 2// c = 1 (since f(n) = O(n^1))// log_2(4) = 2// Since log_b(a) = 2 > c = 1, Case 1 applies (leaf dominated).// Total Complexity: Theta(n^2)Compare log_b(a) with the exponent c of f(n).
Exercise 2: State the recurrence relation for Binary Sear
State the recurrence relation for Binary Search on a sorted array of size n and solve for its time complexity using the Master Theorem.
Explore a worked solution
// Binary Search divides the problem into 1 subproblem of half size with O(1) comparison work:// T(n) = 1T(n/2) + O(1)// a = 1, b = 2, c = 0 (since O(1) = O(n^0))// log_2(1) = 0 == c = 0 -> Case 2 applies.// Complexity: Theta(n^0 * log n) = Theta(log n)In each step of binary search, how many subproblems do you explore?
What stayed with you?
Check the ideas while they’re fresh. Your answers stay in this page and feedback appears as you go.
Exercise 1: Using the Master Theorem determine the tight
Using the Master Theorem, determine the tight asymptotic time complexity of T(n) = 4T(n/2) + O(n). Identify a, b, c and which case applies.
Build successful. (Java 15) [Process exited normally]
Keep exploring.
The official references behind this lesson, when you want a second angle or the full details.
Pause. Put the pieces together.
You’ve reached the end of Asymptotic Analysis: Big-O, Big-Omega & Amortized Complexity. Before moving on, use this task to check what you can do independently.
Solve recurrence relations and prove amortized bounds for dynamic array doubling.
Try it in your own environment and write down the result. This is a self-check; reading completion does not evaluate your code.
Review this moduleOne lesson closer.
Reading is a start. Trying it yourself makes the connection.