Time & Space Complexity - Learning Module

Loading content...

0/276

Time Complexity from Recurrence Relations

The Challenge of Recursive Complexity

Analyzing the time complexity of iterative algorithms is relatively straightforward: count the loops, multiply by the work done per iteration, and you have your answer. But recursive algorithms present a unique challenge. When a function calls itself—potentially multiple times, with different input sizes—how do we determine the total work performed?

This question isn't merely academic. The difference between an O(n) and O(2ⁿ) recursive algorithm could mean the difference between a solution that runs in milliseconds and one that takes longer than the age of the universe. Understanding how to analyze recursive complexity is essential for any engineer who wants to predict algorithm behavior before deploying to production.

What You Will Learn

By the end of this page, you will understand what recurrence relations are, how to write them for recursive algorithms, and the fundamental techniques for solving them to determine time complexity. You'll be able to look at any recursive function and systematically derive its Big-O performance.

Why Iterative Analysis Fails for Recursion

Let's start with why our standard complexity analysis tools don't work directly for recursive functions.

Iterative analysis relies on a clear loop structure:

iterative_sum.py
1
2
3
4
5
6
7
8
def iterative_sum(arr):
    """Sum all elements in an array - O(n) time."""
    total = 0
    for x in arr:       # Loop runs n times
        total += x      # O(1) work per iteration
    return total
    
# Analysis: n iterations × O(1) work = O(n) total

The analysis above is direct: count the iterations, multiply by the work per iteration. But now consider the recursive equivalent:

recursive_sum.py
1
2
3
4
5
6
7
8
9
def recursive_sum(arr, i=0):
    """Sum all elements recursively."""
    if i == len(arr):           # Base case
        return 0
    return arr[i] + recursive_sum(arr, i + 1)  # Recursive case
    
# Analysis: ???
# How many times does this function execute?
# What's the total work across all executions?

The recursive version doesn't have an obvious loop to count. Instead, the function repeatedly calls itself, each call triggering another call, until we reach the base case. The "loop" is implicit in the call structure.

The fundamental problem:

With recursion, we need to reason about:

How many times the function is called (the depth and branching of the call tree)
How much work is done in each call (excluding the recursive calls themselves)
How these factors combine across the entire recursion tree

This is where recurrence relations become essential—they give us a mathematical framework to express and solve these recursive relationships.

The Implicit Loop

Every recursive algorithm can be understood as an implicit loop where the 'iteration count' is determined by the structure of recursive calls. Recurrence relations formalize this implicit structure into an equation we can solve.

What Is a Recurrence Relation?

A recurrence relation is an equation that defines a function in terms of its value on smaller inputs. In the context of algorithm analysis, a recurrence relation expresses the time complexity T(n) of a recursive algorithm in terms of T on smaller problem sizes.

The key insight: A recurrence relation captures the recursive structure of the algorithm mathematically, allowing us to reason about the total work without tracing through every call.

General form of a recurrence:

1
2
3
4
5
6
7
8
T(n) = [number of recursive calls] × T([size of subproblem]) + [work done outside recursive calls]
 
Example: T(n) = 2·T(n/2) + O(n)
 
This means:
- The algorithm makes 2 recursive calls
- Each call is on a problem of size n/2
- Outside the recursive calls, O(n) work is done (at this level)

Components of a recurrence relation:

Anatomy of a Recurrence

•T(n) — The time complexity function we're trying to find. T(n) represents the total time to solve a problem of size n.
•Recursive terms — Terms like T(n/2) or T(n-1) that represent the time for recursive subproblems. These capture the 'dividing' aspect of recursive algorithms.
•Multiplier — The coefficient before recursive terms (e.g., 2·T(n/2)) indicates how many recursive calls are made at each level.
•Non-recursive work — The f(n) term (often O(1), O(n), etc.) representing work done at the current level excluding recursive calls.
•Base case — T(1) = O(1) or similar, representing the time for the smallest subproblem that doesn't recurse further.

The Recurrence as a Story

Think of a recurrence as telling a story: 'To solve a problem of size n, I first do some work [f(n)], then I solve [a] problems of size [n/b], and my answer combines all of that.' The recurrence is this story written in mathematical notation.

Writing Recurrence Relations from Code

The skill of writing recurrence relations from code is fundamental to recursive analysis. Let's develop this skill systematically through increasingly complex examples.

Example 1: Linear Recursion (Single Recursive Call)

factorial.py
1
2
3
4
5
def factorial(n):
    if n <= 1:                    # Base case: O(1)
        return 1
    return n * factorial(n - 1)   # One recursive call on (n-1)
                                  # Plus O(1) multiplication

Deriving the recurrence:

Base case: When n ≤ 1, we do constant work → T(1) = O(1)
Recursive case: We make one call on factorial(n-1) → that's T(n-1)
Non-recursive work: One multiplication → O(1)

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

Example 2: Binary Recursion (Two Recursive Calls)

fibonacci_naive.py
1
2
3
4
5
def fibonacci(n):
    if n <= 1:                              # Base case: O(1)
        return n
    return fibonacci(n-1) + fibonacci(n-2) # TWO recursive calls
                                            # Plus O(1) addition

Deriving the recurrence:

Base case: T(0) = T(1) = O(1)
Recursive case: Two calls: fibonacci(n-1) + fibonacci(n-2)
Non-recursive work: One addition → O(1)

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

Important: This recurrence is more complex because the subproblem sizes differ. We'll see this leads to exponential complexity.

Example 3: Divide-and-Conquer (Halving the Problem)

binary_search.py
1
2
3
4
5
6
7
8
9
10
def binary_search(arr, target, lo, hi):
    if lo > hi:                           # Base case: O(1)
        return -1
    mid = (lo + hi) // 2                  # O(1) computation
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)   # ONE call on n/2
    else:
        return binary_search(arr, target, lo, mid - 1)   # OR ONE call on n/2

Deriving the recurrence:

Base case: T(1) = O(1)
Recursive case: ONE call (not both!) on a problem of size n/2
Non-recursive work: Index computation and comparison → O(1)

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

Example 4: Divide-and-Conquer with Linear Work

merge_sort.py
1
2
3
4
5
6
7
def merge_sort(arr):
    if len(arr) <= 1:                      # Base case: O(1)
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])           # Recursive call on n/2 elements
    right = merge_sort(arr[mid:])          # Recursive call on n/2 elements
    return merge(left, right)              # Merge step: O(n) work

Deriving the recurrence:

Base case: T(1) = O(1)
Recursive case: TWO calls, each on n/2 elements → 2·T(n/2)
Non-recursive work: Merging two sorted halves → O(n)

Recurrence: T(n) = 2·T(n/2) + O(n)

Count Carefully

A common mistake is counting both branches in binary search as 2·T(n/2). Remember: only ONE branch executes per call (it's an if-else). Merge sort, in contrast, executes BOTH branches (left and right sorting), hence 2·T(n/2).

Solving Recurrences: The Expansion Method

The most intuitive technique for solving recurrences is expansion (also called the iteration method or unfolding). We repeatedly substitute the recurrence into itself until we see a pattern.

Solving T(n) = T(n-1) + O(1):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
T(n) = T(n-1) + c           where c = O(1)
 
Expand T(n-1):
T(n) = [T(n-2) + c] + c
     = T(n-2) + 2c
 
Expand T(n-2):
T(n) = [T(n-3) + c] + 2c
     = T(n-3) + 3c
 
Pattern emerges:
T(n) = T(n-k) + k·c
 
We reach base case when n-k = 1, so k = n-1:
T(n) = T(1) + (n-1)·c
     = c + (n-1)·c
     = n·c
     = O(n)
 
✓ Factorial has O(n) time complexity

Solving T(n) = T(n/2) + O(1):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
T(n) = T(n/2) + c           where c = O(1)
 
Expand T(n/2):
T(n) = [T(n/4) + c] + c
     = T(n/4) + 2c
 
Expand T(n/4):
T(n) = [T(n/8) + c] + 2c
     = T(n/8) + 3c
 
Pattern emerges:
T(n) = T(n/2^k) + k·c
 
We reach base case when n/2^k = 1, so 2^k = n, meaning k = log₂(n):
T(n) = T(1) + log₂(n)·c
     = c + c·log₂(n)
     = O(log n)
 
✓ Binary search has O(log n) time complexity

Solving T(n) = 2·T(n/2) + O(n):

This is the merge sort recurrence, which is slightly more complex:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
T(n) = 2·T(n/2) + cn        where cn represents O(n) work
 
Expand:
T(n) = 2·[2·T(n/4) + c(n/2)] + cn
     = 4·T(n/4) + cn + cn
     = 4·T(n/4) + 2cn
 
Expand again:
T(n) = 4·[2·T(n/8) + c(n/4)] + 2cn
     = 8·T(n/8) + cn + 2cn
     = 8·T(n/8) + 3cn
 
Pattern:
T(n) = 2^k · T(n/2^k) + k·cn
 
At base case, n/2^k = 1 → k = log₂(n):
T(n) = 2^(log n) · T(1) + log₂(n) · cn
     = n · c + cn·log(n)
     = O(n) + O(n log n)
     = O(n log n)
 
✓ Merge sort has O(n log n) time complexity

The Art of Pattern Recognition

The key to the expansion method is recognizing when the pattern stabilizes. After 2-3 expansions, look for the general term and express it as T(n) = [something involving k]. Then find what value of k brings you to the base case.

Solving Recurrences: The Recursion Tree Method

The recursion tree method provides a visual approach to solving recurrences. We draw the tree of recursive calls and sum up the work at each level.

Visualizing T(n) = 2·T(n/2) + cn (Merge Sort):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Level 0:           [  n  ]               Cost: cn
                    /      \
Level 1:       [n/2]      [n/2]           Cost: 2 × c(n/2) = cn
               /   \      /   \
Level 2:    [n/4] [n/4] [n/4] [n/4]       Cost: 4 × c(n/4) = cn
              ...                          ...
 
Level k:   [n/2^k] × 2^k nodes            Cost: 2^k × c(n/2^k) = cn
 
Level log(n): [1] × n nodes               Cost: cn (base cases)
 
Key observations:
• Tree has log₂(n) + 1 levels (from n down to 1)
• Each level does exactly cn work
• Total = cn × (log n + 1) = O(n log n)

Visualizing T(n) = T(n-1) + O(1) (Factorial):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Level 0:     [n]      Cost: c
                |
Level 1:    [n-1]     Cost: c
                |
Level 2:    [n-2]     Cost: c
                |
             ...
                |
Level n-1:   [1]      Cost: c
 
Observations:
• Tree is a single chain (no branching)
• n levels, each doing c work
• Total = n × c = O(n)

Visualizing T(n) = 2·T(n-1) + O(1) (Exponential):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Level 0:           [n]                    Cost: c         = c × 2^0
                  /    \
Level 1:       [n-1]  [n-1]               Cost: 2c        = c × 2^1
              /  \    /   \
Level 2:  [n-2][n-2][n-2][n-2]            Cost: 4c        = c × 2^2
           ...
 
Level k:       2^k nodes                   Cost: c × 2^k
 
Level n-1:     2^(n-1) nodes               Cost: c × 2^(n-1)
 
Total = c × (2^0 + 2^1 + 2^2 + ... + 2^(n-1))
      = c × (2^n - 1)
      = O(2^n)
 
⚠️ EXPONENTIAL! Every level doubles the work!

Tree Shape Determines Complexity

The recursion tree reveals complexity through its shape: A chain (factorial) → O(depth). A balanced tree with constant work per level (merge sort) → O(depth × nodes per level). A tree that doubles each level (naive Fibonacci) → O(2^depth). The shape tells the story.

Common Recurrence Patterns and Their Solutions

With practice, you'll recognize common recurrence patterns and their solutions instantly. Here are the essential patterns every engineer should know:

Essential Recurrence Patterns
Recurrence	Solution	Example Algorithm	Intuition
T(n) = T(n-1) + O(1)	O(n)	Factorial, linear search	Chain of n calls, O(1) each
T(n) = T(n-1) + O(n)	O(n²)	Selection sort, insertion sort	Chain of n calls, O(n) each on average
T(n) = T(n/2) + O(1)	O(log n)	Binary search	Halving problem each call, constant work
T(n) = T(n/2) + O(n)	O(n)	Finding median (select)	Linear work shrinks geometrically
T(n) = 2·T(n/2) + O(1)	O(n)	Tree traversal	Work at leaves dominates
T(n) = 2·T(n/2) + O(n)	O(n log n)	Merge sort, quicksort (average)	Balanced tree, linear work per level
T(n) = 2·T(n-1) + O(1)	O(2ⁿ)	Tower of Hanoi, subset enumeration	Doubling tree, exponential nodes
T(n) = T(n-1) + T(n-2) + O(1)	O(φⁿ) ≈ O(1.618ⁿ)	Naive Fibonacci	Fibonacci-growth tree

Why these patterns matter:

Recognizing these patterns allows you to analyze recursive algorithms at a glance:

See T(n) = 2·T(n/2) + O(n)? That's O(n log n). Merge sort, good quicksort.
See T(n) = T(n-1) + O(n)? That's O(n²). Bubble sort, bad quicksort pivot.
See two recursive calls decreasing by 1? That's exponential. Needs memoization.

This pattern recognition accelerates your analysis from minutes of expansion to seconds of recognition.

The Two Key Questions

When you see a recursive function, ask: (1) How many recursive calls? (2) By how much does the problem shrink? If calls = 1 and shrink by half → O(log n). If calls = 2 and shrink by half → O(n log n) or O(n). If calls = 2 and shrink by 1 → exponential. These rules cover 90% of cases.

Practical Application: Analyzing Real Recursive Code

Let's apply our knowledge to analyze real recursive code, walking through the complete process from code to recurrence to solution.

Example: Power Function

power.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def power_naive(x, n):
    """Compute x^n using naive recursion."""
    if n == 0:
        return 1
    return x * power_naive(x, n - 1)
 
def power_fast(x, n):
    """Compute x^n using fast exponentiation."""
    if n == 0:
        return 1
    if n % 2 == 0:
        half = power_fast(x, n // 2)
        return half * half
    else:
        return x * power_fast(x, n - 1)

Analysis of power_naive:

Recurrence: T(n) = T(n-1) + O(1)
Solution: O(n)

Analysis of power_fast:

The even case halves n, the odd case decreases n by 1 (making it even). At most, every other call is odd, so effectively we halve n approximately every two calls.

Recurrence: T(n) = T(n/2) + O(1)  (approximately)
Solution: O(log n)

The fast version is exponentially better—computing 2^1000 takes ~10 steps instead of 1000!

Example: Maximum Element in Array

max_element.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def find_max_linear(arr, i=0):
    """Find maximum using linear recursion."""
    if i == len(arr) - 1:
        return arr[i]
    return max(arr[i], find_max_linear(arr, i + 1))
 
def find_max_divide(arr, lo, hi):
    """Find maximum using divide and conquer."""
    if lo == hi:
        return arr[lo]
    mid = (lo + hi) // 2
    left_max = find_max_divide(arr, lo, mid)
    right_max = find_max_divide(arr, mid + 1, hi)
    return max(left_max, right_max)

Both have O(n) time complexity, but different recurrences:

Linear version:     T(n) = T(n-1) + O(1) → O(n)
Divide version:     T(n) = 2·T(n/2) + O(1) → O(n)

Interesting! The divide-and-conquer approach doesn't improve complexity here because we still must examine every element. However, divide-and-conquer offers parallelization potential—the two halves can be processed simultaneously on different cores.

Same Complexity ≠ Same Algorithm

Two algorithms with the same Big-O can have very different practical characteristics. Divide-and-conquer enables parallelization, has different cache behavior, and may have different constant factors. Complexity is essential but not the whole story.

Summary: Analyzing Recursive Time Complexity

We've covered the fundamental approach to analyzing recursive time complexity. Let's consolidate the key concepts:

Key Takeaways

•Recurrence relations express recursive structure mathematically — They capture how total work T(n) depends on work for smaller subproblems.
•Writing recurrences from code requires identifying three things — The number of recursive calls, the size of subproblems, and the non-recursive work at each call.
•The expansion method solves recurrences by substitution — Expand repeatedly until a pattern emerges, then find the base case condition.
•Recursion trees visualize the work structure — Sum work across all levels to find total complexity.
•Pattern recognition accelerates analysis — Common patterns (halving, linear reduction, doubling) have known solutions.
•The shape of recursive calls determines complexity class — One call with halving → log n. Two calls with halving → n log n. Two calls with linear reduction → exponential.

What's next:

Understanding time complexity is only half the picture. Recursive algorithms also consume memory through the call stack. In the next page, we'll explore space complexity for recursive algorithms—understanding how stack depth affects memory usage and how to reason about the hidden space cost of recursion.

Page Complete

You now understand how to analyze the time complexity of recursive algorithms using recurrence relations. You can write recurrences from code, solve them through expansion and recursion trees, and recognize common patterns. Next, we'll tackle the space complexity dimension of recursive analysis.

Time Complexity from Recurrence Relations

The Challenge of Recursive Complexity

What You Will Learn

Why Iterative Analysis Fails for Recursion

Let's start with why our standard complexity analysis tools don't work directly for recursive functions.

Iterative analysis relies on a clear loop structure:

iterative_sum.py
1
2
3
4
5
6
7
8
def iterative_sum(arr):
    """Sum all elements in an array - O(n) time."""
    total = 0
    for x in arr:       # Loop runs n times
        total += x      # O(1) work per iteration
    return total
    
# Analysis: n iterations × O(1) work = O(n) total

The analysis above is direct: count the iterations, multiply by the work per iteration. But now consider the recursive equivalent:

recursive_sum.py
1
2
3
4
5
6
7
8
9
def recursive_sum(arr, i=0):
    """Sum all elements recursively."""
    if i == len(arr):           # Base case
        return 0
    return arr[i] + recursive_sum(arr, i + 1)  # Recursive case
    
# Analysis: ???
# How many times does this function execute?
# What's the total work across all executions?

The fundamental problem:

With recursion, we need to reason about:

How many times the function is called (the depth and branching of the call tree)
How much work is done in each call (excluding the recursive calls themselves)
How these factors combine across the entire recursion tree

This is where recurrence relations become essential—they give us a mathematical framework to express and solve these recursive relationships.

The Implicit Loop

What Is a Recurrence Relation?

The key insight: A recurrence relation captures the recursive structure of the algorithm mathematically, allowing us to reason about the total work without tracing through every call.

General form of a recurrence:

1
2
3
4
5
6
7
8
T(n) = [number of recursive calls] × T([size of subproblem]) + [work done outside recursive calls]
 
Example: T(n) = 2·T(n/2) + O(n)
 
This means:
- The algorithm makes 2 recursive calls
- Each call is on a problem of size n/2
- Outside the recursive calls, O(n) work is done (at this level)

Components of a recurrence relation:

Anatomy of a Recurrence

•T(n) — The time complexity function we're trying to find. T(n) represents the total time to solve a problem of size n.
•Recursive terms — Terms like T(n/2) or T(n-1) that represent the time for recursive subproblems. These capture the 'dividing' aspect of recursive algorithms.
•Multiplier — The coefficient before recursive terms (e.g., 2·T(n/2)) indicates how many recursive calls are made at each level.
•Non-recursive work — The f(n) term (often O(1), O(n), etc.) representing work done at the current level excluding recursive calls.
•Base case — T(1) = O(1) or similar, representing the time for the smallest subproblem that doesn't recurse further.

The Recurrence as a Story

Writing Recurrence Relations from Code

The skill of writing recurrence relations from code is fundamental to recursive analysis. Let's develop this skill systematically through increasingly complex examples.

Example 1: Linear Recursion (Single Recursive Call)

factorial.py
1
2
3
4
5
def factorial(n):
    if n <= 1:                    # Base case: O(1)
        return 1
    return n * factorial(n - 1)   # One recursive call on (n-1)
                                  # Plus O(1) multiplication

Deriving the recurrence:

Base case: When n ≤ 1, we do constant work → T(1) = O(1)
Recursive case: We make one call on factorial(n-1) → that's T(n-1)
Non-recursive work: One multiplication → O(1)

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

Example 2: Binary Recursion (Two Recursive Calls)

fibonacci_naive.py
1
2
3
4
5
def fibonacci(n):
    if n <= 1:                              # Base case: O(1)
        return n
    return fibonacci(n-1) + fibonacci(n-2) # TWO recursive calls
                                            # Plus O(1) addition

Deriving the recurrence:

Base case: T(0) = T(1) = O(1)
Recursive case: Two calls: fibonacci(n-1) + fibonacci(n-2)
Non-recursive work: One addition → O(1)

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

Important: This recurrence is more complex because the subproblem sizes differ. We'll see this leads to exponential complexity.

Example 3: Divide-and-Conquer (Halving the Problem)

binary_search.py
1
2
3
4
5
6
7
8
9
10
def binary_search(arr, target, lo, hi):
    if lo > hi:                           # Base case: O(1)
        return -1
    mid = (lo + hi) // 2                  # O(1) computation
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)   # ONE call on n/2
    else:
        return binary_search(arr, target, lo, mid - 1)   # OR ONE call on n/2

Deriving the recurrence:

Base case: T(1) = O(1)
Recursive case: ONE call (not both!) on a problem of size n/2
Non-recursive work: Index computation and comparison → O(1)

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

Example 4: Divide-and-Conquer with Linear Work

merge_sort.py
1
2
3
4
5
6
7
def merge_sort(arr):
    if len(arr) <= 1:                      # Base case: O(1)
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])           # Recursive call on n/2 elements
    right = merge_sort(arr[mid:])          # Recursive call on n/2 elements
    return merge(left, right)              # Merge step: O(n) work

Deriving the recurrence:

Base case: T(1) = O(1)
Recursive case: TWO calls, each on n/2 elements → 2·T(n/2)
Non-recursive work: Merging two sorted halves → O(n)

Recurrence: T(n) = 2·T(n/2) + O(n)

Count Carefully

Solving Recurrences: The Expansion Method

The most intuitive technique for solving recurrences is expansion (also called the iteration method or unfolding). We repeatedly substitute the recurrence into itself until we see a pattern.

Solving T(n) = T(n-1) + O(1):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
T(n) = T(n-1) + c           where c = O(1)
 
Expand T(n-1):
T(n) = [T(n-2) + c] + c
     = T(n-2) + 2c
 
Expand T(n-2):
T(n) = [T(n-3) + c] + 2c
     = T(n-3) + 3c
 
Pattern emerges:
T(n) = T(n-k) + k·c
 
We reach base case when n-k = 1, so k = n-1:
T(n) = T(1) + (n-1)·c
     = c + (n-1)·c
     = n·c
     = O(n)
 
✓ Factorial has O(n) time complexity

Solving T(n) = T(n/2) + O(1):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
T(n) = T(n/2) + c           where c = O(1)
 
Expand T(n/2):
T(n) = [T(n/4) + c] + c
     = T(n/4) + 2c
 
Expand T(n/4):
T(n) = [T(n/8) + c] + 2c
     = T(n/8) + 3c
 
Pattern emerges:
T(n) = T(n/2^k) + k·c
 
We reach base case when n/2^k = 1, so 2^k = n, meaning k = log₂(n):
T(n) = T(1) + log₂(n)·c
     = c + c·log₂(n)
     = O(log n)
 
✓ Binary search has O(log n) time complexity

Solving T(n) = 2·T(n/2) + O(n):

This is the merge sort recurrence, which is slightly more complex:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
T(n) = 2·T(n/2) + cn        where cn represents O(n) work
 
Expand:
T(n) = 2·[2·T(n/4) + c(n/2)] + cn
     = 4·T(n/4) + cn + cn
     = 4·T(n/4) + 2cn
 
Expand again:
T(n) = 4·[2·T(n/8) + c(n/4)] + 2cn
     = 8·T(n/8) + cn + 2cn
     = 8·T(n/8) + 3cn
 
Pattern:
T(n) = 2^k · T(n/2^k) + k·cn
 
At base case, n/2^k = 1 → k = log₂(n):
T(n) = 2^(log n) · T(1) + log₂(n) · cn
     = n · c + cn·log(n)
     = O(n) + O(n log n)
     = O(n log n)
 
✓ Merge sort has O(n log n) time complexity

The Art of Pattern Recognition

Solving Recurrences: The Recursion Tree Method

The recursion tree method provides a visual approach to solving recurrences. We draw the tree of recursive calls and sum up the work at each level.

Visualizing T(n) = 2·T(n/2) + cn (Merge Sort):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Level 0:           [  n  ]               Cost: cn
                    /      \
Level 1:       [n/2]      [n/2]           Cost: 2 × c(n/2) = cn
               /   \      /   \
Level 2:    [n/4] [n/4] [n/4] [n/4]       Cost: 4 × c(n/4) = cn
              ...                          ...
 
Level k:   [n/2^k] × 2^k nodes            Cost: 2^k × c(n/2^k) = cn
 
Level log(n): [1] × n nodes               Cost: cn (base cases)
 
Key observations:
• Tree has log₂(n) + 1 levels (from n down to 1)
• Each level does exactly cn work
• Total = cn × (log n + 1) = O(n log n)

Visualizing T(n) = T(n-1) + O(1) (Factorial):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Level 0:     [n]      Cost: c
                |
Level 1:    [n-1]     Cost: c
                |
Level 2:    [n-2]     Cost: c
                |
             ...
                |
Level n-1:   [1]      Cost: c
 
Observations:
• Tree is a single chain (no branching)
• n levels, each doing c work
• Total = n × c = O(n)

Visualizing T(n) = 2·T(n-1) + O(1) (Exponential):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Level 0:           [n]                    Cost: c         = c × 2^0
                  /    \
Level 1:       [n-1]  [n-1]               Cost: 2c        = c × 2^1
              /  \    /   \
Level 2:  [n-2][n-2][n-2][n-2]            Cost: 4c        = c × 2^2
           ...
 
Level k:       2^k nodes                   Cost: c × 2^k
 
Level n-1:     2^(n-1) nodes               Cost: c × 2^(n-1)
 
Total = c × (2^0 + 2^1 + 2^2 + ... + 2^(n-1))
      = c × (2^n - 1)
      = O(2^n)
 
⚠️ EXPONENTIAL! Every level doubles the work!

Tree Shape Determines Complexity

Common Recurrence Patterns and Their Solutions

With practice, you'll recognize common recurrence patterns and their solutions instantly. Here are the essential patterns every engineer should know:

Essential Recurrence Patterns
Recurrence	Solution	Example Algorithm	Intuition
T(n) = T(n-1) + O(1)	O(n)	Factorial, linear search	Chain of n calls, O(1) each
T(n) = T(n-1) + O(n)	O(n²)	Selection sort, insertion sort	Chain of n calls, O(n) each on average
T(n) = T(n/2) + O(1)	O(log n)	Binary search	Halving problem each call, constant work
T(n) = T(n/2) + O(n)	O(n)	Finding median (select)	Linear work shrinks geometrically
T(n) = 2·T(n/2) + O(1)	O(n)	Tree traversal	Work at leaves dominates
T(n) = 2·T(n/2) + O(n)	O(n log n)	Merge sort, quicksort (average)	Balanced tree, linear work per level
T(n) = 2·T(n-1) + O(1)	O(2ⁿ)	Tower of Hanoi, subset enumeration	Doubling tree, exponential nodes
T(n) = T(n-1) + T(n-2) + O(1)	O(φⁿ) ≈ O(1.618ⁿ)	Naive Fibonacci	Fibonacci-growth tree

Why these patterns matter:

Recognizing these patterns allows you to analyze recursive algorithms at a glance:

See T(n) = 2·T(n/2) + O(n)? That's O(n log n). Merge sort, good quicksort.
See T(n) = T(n-1) + O(n)? That's O(n²). Bubble sort, bad quicksort pivot.
See two recursive calls decreasing by 1? That's exponential. Needs memoization.

This pattern recognition accelerates your analysis from minutes of expansion to seconds of recognition.

The Two Key Questions

Practical Application: Analyzing Real Recursive Code

Let's apply our knowledge to analyze real recursive code, walking through the complete process from code to recurrence to solution.

Example: Power Function

power.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def power_naive(x, n):
    """Compute x^n using naive recursion."""
    if n == 0:
        return 1
    return x * power_naive(x, n - 1)
 
def power_fast(x, n):
    """Compute x^n using fast exponentiation."""
    if n == 0:
        return 1
    if n % 2 == 0:
        half = power_fast(x, n // 2)
        return half * half
    else:
        return x * power_fast(x, n - 1)

Analysis of power_naive:

Recurrence: T(n) = T(n-1) + O(1)
Solution: O(n)

Analysis of power_fast:

The even case halves n, the odd case decreases n by 1 (making it even). At most, every other call is odd, so effectively we halve n approximately every two calls.

Recurrence: T(n) = T(n/2) + O(1)  (approximately)
Solution: O(log n)

The fast version is exponentially better—computing 2^1000 takes ~10 steps instead of 1000!

Example: Maximum Element in Array

max_element.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def find_max_linear(arr, i=0):
    """Find maximum using linear recursion."""
    if i == len(arr) - 1:
        return arr[i]
    return max(arr[i], find_max_linear(arr, i + 1))
 
def find_max_divide(arr, lo, hi):
    """Find maximum using divide and conquer."""
    if lo == hi:
        return arr[lo]
    mid = (lo + hi) // 2
    left_max = find_max_divide(arr, lo, mid)
    right_max = find_max_divide(arr, mid + 1, hi)
    return max(left_max, right_max)

Both have O(n) time complexity, but different recurrences:

Linear version:     T(n) = T(n-1) + O(1) → O(n)
Divide version:     T(n) = 2·T(n/2) + O(1) → O(n)

Same Complexity ≠ Same Algorithm

Summary: Analyzing Recursive Time Complexity

We've covered the fundamental approach to analyzing recursive time complexity. Let's consolidate the key concepts:

Key Takeaways

•Recurrence relations express recursive structure mathematically — They capture how total work T(n) depends on work for smaller subproblems.
•Writing recurrences from code requires identifying three things — The number of recursive calls, the size of subproblems, and the non-recursive work at each call.
•The expansion method solves recurrences by substitution — Expand repeatedly until a pattern emerges, then find the base case condition.
•Recursion trees visualize the work structure — Sum work across all levels to find total complexity.
•Pattern recognition accelerates analysis — Common patterns (halving, linear reduction, doubling) have known solutions.
•The shape of recursive calls determines complexity class — One call with halving → log n. Two calls with halving → n log n. Two calls with linear reduction → exponential.

What's next:

Page Complete