Recurrences and Step-by-Step Trace Tool

Recurrences and Step-by-Step Trace Tool

What is a Recurrence?

A recurrence relation defines a function in terms of itself with smaller inputs.

Common Recurrence Patterns

1. T(n) = T(n/2) + O(1)

• Solution: T(n) = O(log n)
• Example: Binary search

2. T(n) = 2T(n/2) + O(n)

• Solution: T(n) = O(n log n)
• Example: Merge sort

3. T(n) = 2T(n/2) + O(1)

• Solution: T(n) = O(n)
• Example: Tree traversal

4. T(n) = T(n-1) + O(1)

• Solution: T(n) = O(n)
• Example: Linear recursion

Master Theorem

For recurrences: T(n) = aT(n/b) + f(n)

Where a ≥ 1, b > 1, and f(n) is asymptotically positive.

Case 1: f(n) = O(n^(log_b a - ε))

• Solution: T(n) = Θ(n^(log_b a))
• Example: T(n) = 2T(n/2) + n^(0.5)

Case 2: f(n) = Θ(n^(log_b a))

• Solution: T(n) = Θ(n^(log_b a) · log n)
• Example: T(n) = 2T(n/2) + n

Case 3: f(n) = Ω(n^(log_b a + ε)) and af(n/b) ≤ cf(n)

• Solution: T(n) = Θ(f(n))
• Example: T(n) = 2T(n/2) + n²

Substitution Method

1. Guess the form of solution
2. Use induction to prove

Example

T(n) = 2T(n/2) + n

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

Base: T(1) = O(1) = O(1 log 1) ✓

Inductive Step: Assume T(k) ≤ ck log k for k < n

T(n) = 2T(n/2) + n

≤ 2c(n/2) log(n/2) + n

= cn log(n/2) + n

= cn log n - cn log 2 + n

= cn log n - cn + n

≤ cn log n (for c ≥ 1)

Recursion Tree Method

Visualize the recurrence as a tree.

def analyze_recurrence(a, b, f_n, n):
    """
    Analyze recurrence T(n) = aT(n/b) + f(n)
    Returns tree levels and total cost
    """
    levels = []
    level = 0
    size = n
    total_cost = 0
    
    while size >= 1:
        num_nodes = a ** level
        cost_per_level = num_nodes * f_n(size)
        levels.append({
            'level': level,
            'size': size,
            'nodes': num_nodes,
            'cost': cost_per_level
        })
        total_cost += cost_per_level
        size = size // b
        level += 1
    
    return levels, total_cost

Practice Problems

1. Solve T(n) = 3T(n/2) + n using Master Theorem
2. Solve T(n) = T(n-1) + n using substitution
3. Draw recursion tree for T(n) = 4T(n/2) + n²
4. Analyze T(n) = T(√n) + 1
5. Solve T(n) = 2T(n/4) + √n