The Big Picture

Why recurrence analysis matters for algorithm performance

Three-Step Analysis Framework

1

Write the recurrence relation

Express algorithm's runtime in terms of smaller subproblems

2

Solve the recurrence relation

Use Master Method, Substitution, or Recursion Tree

3

Express in asymptotic notation

Present final result as Θ(f(n)), O(f(n)), or Ω(f(n))

Why This Matters

Algorithm Performance

Know if your divide-and-conquer algorithm is O(n log n) or O(n²)

Design Decisions

Choose the right algorithmic approach for your problem

Practical Impact

Difference between seconds and hours for large datasets

Common Recurrence Examples

Binary Search

T(n) = T(n/2) + O(1)
Result: Θ(log n)

Merge Sort

T(n) = 2T(n/2) + O(n)
Result: Θ(n log n)

Tree Traversal

T(n) = 2T(n/2) + O(1)
Result: Θ(n)

Divide & Conquer Foundation

Generic form T(n) = aT(n/b) + f(n) and tree analysis

Generic Divide & Conquer Recurrence

T(n) = aT(n/b) + f(n)
a: Number of subproblems
n/b: Size of each subproblem
f(n): Cost of divide + combine steps

Tree Analysis Intuition

T(n)

Key Tree Properties

Tree Height: log_b(n)
Number of Leaves: a^(log_b n) = n^(log_b a)
Work per Level: Varies by problem
Total Work: Sum across all levels

Analysis Strategy

1. Identify Work Distribution

Is work concentrated at root, leaves, or balanced across levels?

2. Compare f(n) with n^(log_b a)

This comparison determines which dominates the runtime

3. Apply Appropriate Method

Master Method for standard form, otherwise substitution or recursion tree

Master Method

Three cases plus non-applicable examples

Case 1: Leaves Dominate

Condition: f(n) = O(n^(log_b a - ε)) for some ε > 0
Result: T(n) = Θ(n^(log_b a))

Example: T(n) = 8T(n/2) + n²

a = 8, b = 2, f(n) = n²
n^(log_b a) = n^(log_2 8) = n³
n² = O(n^(3-1)) = O(n²) ✓
Therefore: T(n) = Θ(n³)

Case 2: Balanced Work

Condition: f(n) = Θ(n^(log_b a) log^k n) for k ≥ 0
Result: T(n) = Θ(n^(log_b a) log^(k+1) n)

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

a = 2, b = 2, f(n) = n
n^(log_b a) = n^(log_2 2) = n¹ = n
f(n) = n = Θ(n × log⁰ n) ✓
Therefore: T(n) = Θ(n log n)

Case 3: Root Dominates

Condition: f(n) = Ω(n^(log_b a + ε)) for some ε > 0, plus regularity condition
Result: T(n) = Θ(f(n))

Example: T(n) = 2T(n/2) + n²

a = 2, b = 2, f(n) = n²
n^(log_b a) = n^(log_2 2) = n
n² = Ω(n^(1+1)) = Ω(n²) ✓
Regularity: af(n/b) = 2(n/2)² = n²/2 ≤ cn² for c = 1/2 ✓
Therefore: T(n) = Θ(n²)

When Master Method Fails

Gap Case: T(n) = 2T(n/2) + n log log n

f(n) falls between polynomial bounds - no clear case applies

Different Subproblem Sizes: T(n) = T(n/3) + T(2n/3) + n

Subproblems have different sizes - Master Method form doesn't apply

Regularity Condition Fails: T(n) = 2T(n/2) + n² sin n

f(n) is polynomially larger but regularity condition doesn't hold

Substitution Method

Complete proof technique with detailed example

Method Steps

1

Guess the solution

Make an educated guess about the form of the solution

2

Prove by induction

Use mathematical induction to verify the guess

3

Handle base cases

Ensure the solution works for small values

Complete Example: T(n) = 2T(n/2) + n

Step 1: Initial Guess

T(n) ≤ cn log n

Based on merge sort pattern and tree analysis suggesting O(n log n)

Step 2: Inductive Hypothesis

Assume T(k) ≤ ck log k for all k < n

Step 3: Inductive Step

T(n) = 2T(n/2) + n
≤ 2 · c(n/2) log(n/2) + n
= cn log(n/2) + n
= cn(log n - log 2) + n
= cn log n - cn log 2 + n
= cn log n + n(1 - c log 2)

For this to be ≤ cn log n, we need 1 - c log 2 ≤ 0, so c ≥ 1/log 2

Step 4: Base Case Problem

Issue: T(1) = 1, but c·1·log 1 = 0

We need 1 ≤ 0, which is impossible!

Step 5: Refined Guess

T(n) ≤ cn log n + d

Adding a constant term to handle base cases

T(n) = 2T(n/2) + n
≤ 2(c(n/2) log(n/2) + d) + n
= cn log n - cn log 2 + 2d + n
= cn log n + n(1 - c log 2) + 2d

Choose c ≥ 1/log 2 and d ≥ 1. Then T(1) = 1 ≤ d ✓

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

Key Insights

Choosing Constants

Constants are mathematical tools - they don't affect asymptotic growth

Base Case Handling

Adding lower-order terms often resolves base case issues

Proof Strategy

Start with simple guess, refine if needed for base cases

Alternative Approaches

Recursion trees and insertion sort analysis

Recursion Tree Method

Example: T(n) = 3T(n/4) + cn²

Click "Build Tree" to see visualization

Mathematical Analysis

Tree Height: log₄ n
Leaves: 3^(log₄ n) = n^(log₄ 3) ≈ n^0.79
Work per Level i: 3ⁱ × c(n/4ⁱ)² = cn² × (3/16)ⁱ
Total Work: cn² × ∑(3/16)ⁱ = cn² × (16/13) = Θ(n²)
Key Insight: Since 3/16 < 1, the series converges and root dominates!

Insertion Sort: Inversions Analysis

Interactive Demo

Click demo to see insertion sort analyze inversions

Understanding Inversions

Definition: An inversion is a pair (i,j) where i < j but A[i] > A[j]
Example: Array [5, 2, 4, 1, 3] has 7 inversions:
(0,1): 5>2, (0,2): 5>4, (0,3): 5>1, (0,4): 5>3, (1,3): 2>1, (2,3): 4>1, (2,4): 4>3
Fundamental Insight: Each swap in insertion sort removes exactly one inversion!
Therefore: Runtime = Number of swaps = Number of inversions

Complexity Cases

Best Case: Already sorted
0 inversions → Θ(n) time
Average Case: Random permutation
~n(n-1)/4 inversions → Θ(n²) time
Worst Case: Reverse sorted
n(n-1)/2 inversions → Θ(n²) time

Synthesis

Method comparison and selection criteria

Method Selection Guide

Method
When to Use
Pros
Cons
Master Method
T(n) = aT(n/b) + f(n) form
Fast, systematic, covers most D&C algorithms
Limited to specific form, can have gaps
Substitution Method
Master Method fails, need exact bounds
General purpose, proves tight bounds
Requires good initial guess
Recursion Tree
Building intuition, irregular recurrences
Visual, good for understanding
Can involve complex summations

Decision Process

Is it T(n) = aT(n/b) + f(n)?
↓ YES
Try Master Method
↓ If applicable
Done! ✓
NO →
Use Recursion Tree or Substitution
Build intuition first, then prove

Key Takeaways

Start with Intuition

Always begin by understanding what the algorithm is doing recursively

Tree Mental Model

Think about where work is concentrated: root, leaves, or balanced

Master Method First

If the recurrence fits the form, Master Method is usually fastest

Multiple Approaches

Don't rely on just one method - cross-check your results

Common Algorithm Patterns

Binary Divide

T(n) = 2T(n/2) + O(n^k)
Merge Sort, Quick Sort (avg), etc.

Decrease by Constant

T(n) = T(n-1) + O(n^k)
Selection Sort, Insertion Sort

Logarithmic Reduction

T(n) = T(n/2) + O(1)
Binary Search, Tree Operations

Multiple Subproblems

T(n) = aT(n/b) + O(n^k)
Strassen's Algorithm, etc.

Final Advice

Practice is key! The more recurrences you analyze, the better you'll become at recognizing patterns and choosing the right method.

Build intuition first: Always try to understand what the algorithm is doing before diving into formal analysis.

Double-check your work: Use multiple methods when possible to verify your results.