Asymptotic Analysis — Complete Framework with Recurrence Relations and Master Theorem

Introduction

You now have three tools: Big O (upper bound), Big Omega (lower bound), and Big Theta (tight bound). Asymptotic analysis is the complete framework that uses these tools together to formally characterize algorithm behavior.

But for recursive algorithms — which make up a large portion of important algorithms — simply counting loops is not enough. Recursive algorithms express their running time in terms of their running time on smaller inputs. This creates a recurrence relation, and solving it requires specific mathematical techniques.

This lesson covers:

1. The complete framework of asymptotic analysis
2. How to set up recurrence relations for any recursive algorithm
3. Three methods for solving recurrences: substitution, recursion tree, and Master Theorem
4. How to apply the complete analysis to every major algorithm type

Setting Up Recurrence Relations

A recurrence relation is an equation that defines a function in terms of its value at smaller inputs. For algorithm analysis:

T(n) = the number of operations performed on an input of size n

For recursive algorithms, T(n) is expressed in terms of T(smaller values).

The General Form

Most recursive algorithms produce recurrences of the form:

Example — Binary Search

Setting up the recurrence:

• One recursive call: a = 1
• Input size halves: b = 2 (call on n/2 elements)
• Work outside the call: 1 comparison = O(1)

Recurrence: T(n) = T(n/2) + O(1), T(1) = O(1)

Example — Merge Sort

Setting up the recurrence:

• Two recursive calls: a = 2
• Input size halves: b = 2
• Work outside: O(n) for merging

Recurrence: T(n) = 2T(n/2) + n, T(1) = O(1)

Example — Naive Fibonacci

Setting up the recurrence:

• Two recursive calls, but they do NOT halve the input equally
• The calls are on inputs n-1 and n-2 (subtracting 1 or 2, not dividing)

Recurrence: T(n) = T(n-1) + T(n-2) + O(1), T(0) = T(1) = O(1)

This is not in the standard divide-and-conquer form. It requires a different solution method.

Method 1 — The Substitution Method

The substitution method involves:

1. Guessing the form of the solution
2. Using mathematical induction to prove it

This method is powerful but requires insight to make a good initial guess.

Example — Solving T(n) = T(n/2) + 1

Guess: T(n) = O(log n), i.e., T(n) ≤ c · log n for some constant c.

Prove T(n) ≤ c · log n by induction:

*Assume:* T(k) ≤ c · log k for all k < n (inductive hypothesis)

*Prove for n:*

Conclusion: T(n) = O(log n) ✓

Example — Solving T(n) = 2T(n/2) + n

Guess: T(n) = O(n log n)

Prove T(n) ≤ c · n · log n:

*Assume:* T(k) ≤ c · k · log k for all k < n

*Prove for n:*

Conclusion: T(n) = O(n log n) ✓

Tips for Guessing

• If the recurrence subtracts a constant (T(n-1)), the solution is often polynomial: T(n) = O(n^k)
• If the recurrence divides by a constant (T(n/b)), the solution is often logarithmic or polynomial-log: T(n) = O(log n) or O(n log n)
• If two recursive calls on nearly full-size input (T(n-1) + T(n-2)), the solution is often exponential: T(n) = O(2ⁿ)

Method 2 — The Recursion Tree Method

The recursion tree method draws out the recursive call structure as a tree, calculates the work done at each level, and sums across all levels.

Steps:

1. Draw the recursion tree: each node represents one recursive call
2. Label each node with the non-recursive work at that level
3. Sum the work at each level
4. Sum across all levels

Example — T(n) = 2T(n/2) + n (Merge Sort)

Step 1 — Draw the tree:

Step 2 — Identify the depth: The tree has depth log₂(n), because we keep halving until we reach size 1.

Step 3 — Sum the levels:

• Each of the log n + 1 levels contributes n work
• Total = n × (log n + 1) = n log n + n = O(n log n)

Answer: T(n) = O(n log n) ✓

Example — T(n) = 3T(n/4) + n²

Step 1 — Draw the tree:

Step 2 — Identify the depth: We divide by 4 each time: depth = log₄(n)

Step 3 — Sum the levels:

Answer: T(n) = O(n²)

The non-recursive work (n²) dominates here — the recursive part contributes less than the top level.

Method 3 — The Master Theorem

The Master Theorem provides direct, formulaic solutions for a large class of recurrences of the form:

T(n) = a · T(n/b) + f(n) where a ≥ 1, b > 1

The Three Cases

Let **c\* = log_b(a)** (the "critical exponent").

Case 1 — Recursive work dominates: If f(n) = O(n^(c* - ε)) for some ε > 0 (f grows slower than n^c*)

Then: **T(n) = Θ(n^c*)**

The leaves of the recursion tree do the most work.

Case 2 — Work is balanced at all levels: If f(n) = Θ(n^c* · log^k n) for some k ≥ 0 (f grows at the same rate as n^c*)

Then: **T(n) = Θ(n^c* · log^(k+1) n)**

Common subcase (k=0): If f(n) = Θ(n^c*), then T(n) = Θ(n^c* · log n)

Case 3 — Non-recursive work dominates: If f(n) = Ω(n^(c* + ε)) for some ε > 0 (f grows faster than n^c*) AND f(n/b) ≤ cf(n) for some c < 1 (regularity condition)

Then: T(n) = Θ(f(n))

The root of the recursion tree does the most work.

Applying the Master Theorem — Five Complete Examples

Example 1 — Binary Search: T(n) = T(n/2) + 1

Example 2 — Merge Sort: T(n) = 2T(n/2) + n

Example 3 — T(n) = 4T(n/2) + n (example)

Example 4 — T(n) = 4T(n/2) + n² (example)

Example 5 — T(n) = 4T(n/2) + n³ (example)

When Master Theorem Does Not Apply

The Master Theorem only applies when the recurrence is in the form T(n) = aT(n/b) + f(n). It does NOT apply to:

Linear recurrences (T(n-1), T(n-2), etc.):

When f(n) falls in the gap between cases:

Solving Non-Standard Recurrences

T(n) = T(n-1) + n — Factorial/Simple Recursion

T(n) = T(n-1) + 1 — Linear Recursion

T(n) = 2T(n-1) + 1 — Tower of Hanoi

Complete Analysis Reference

Summary

Asymptotic analysis is the complete mathematical framework for characterizing algorithm efficiency:

• Three notations: O (upper/worst), Ω (lower/best), Θ (tight/average)
• Recurrence relations: Express recursive algorithm complexity as T(n) = aT(n/b) + f(n)
• Three solving methods:
• Substitution: Guess and prove by induction — requires insight, very rigorous
• Recursion Tree: Draw the tree, sum level-by-level — visual and intuitive
• Master Theorem: Direct formula for T(n) = aT(n/b) + f(n) — fastest method when applicable
• The Master Theorem has three cases based on whether f(n) is smaller than, equal to, or larger than n^(log_b(a))
• For non-divide-and-conquer recurrences, use expansion (unrolling) or the recursion tree

Mastery of asymptotic analysis is what separates engineers who can reason about algorithm performance from those who can only measure it empirically after the fact.

*Next Lesson: Best, Average, and Worst Case Analysis — Applying asymptotic analysis to concrete algorithms and understanding how input characteristics affect performance.*