🔬 Analyzing Recursive Algorithms

Beginner Friendly ~20 min read

You know merge sort is fast - but exactly HOW fast? In this lesson, you'll learn a simple visual method to analyze recursive algorithms, plus a powerful shortcut called the Master Theorem that works like magic!

This builds on your complexity intuition from the previous lesson.

💼 The Google Interview Question

Interviewer: "Explain why merge sort is O(n log n)."

Candidate A: "Um... because it's a divide-and-conquer algorithm?" ❌
Result: Rejected. No proof.

Candidate B: "Let me draw the recursion tree..." ✅
Draws tree, counts levels, shows work at each level.
Interviewer: "Perfect! When can you start?"

The difference? Candidate B could prove it, not just memorize it.

Merge Sort Recursion Tree (n=8)

📊 Pattern

Every level does n work total

📏 Depth

Tree has log n levels

🎯 Result

n × log n = O(n log n)

The recursion tree method: Draw it, count the levels, sum the work. That's it!

The Challenge: Analyzing Merge Sort

Let's say you're in a job interview and someone asks: "What's the time complexity of merge sort?"

You might say "O(n log n)" - but then they ask: "How do you KNOW that?"

🤔 The Problem

With loops, you can count iterations. But merge sort calls itself recursively - how do you count that?

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # ← Recursive call
    right = merge_sort(arr[mid:])   # ← Recursive call
    return merge(left, right)       # ← Some work here

Question: How many operations does this do for an array of size n?

Step 1: Draw the Recursion Tree

The best way to understand recursive algorithms is to draw how they break down the problem. Watch this visualization:

💡 What You're Seeing

Merge sort breaks the problem into smaller pieces:

Level 0: Sort array of size n
Level 1: Sort 2 arrays of size n/2
Level 2: Sort 4 arrays of size n/4
Level 3: Sort 8 arrays of size n/8
...and so on until arrays are size 1

Counting Operations by Hand

Let's count the work at each level for an array of size 8:

Level	Number of Arrays	Size of Each	Work Per Array	Total Work
0	1	8	8	8
1	2	4	4	8
2	4	2	2	8
3	8	1	1	8

Pattern Discovered! Each level does exactly n work (8 in this case).
How many levels? log₂(n) levels (because you keep dividing by 2).
Total work = n × log n = O(n log n) ✅

Step 2: Writing the Pattern (Recurrence Relation)

Instead of drawing trees every time, you can write this pattern as a formula:

For Merge Sort:

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

Translation:

T(n) = Time to sort n elements
2 × T(n/2) = Sort two halves (each of size n/2)
+ n = Merge the halves back together (n operations)

This is called a recurrence relation - it's just a way to write "the time for n depends on the time for smaller problems."

Example: Binary Search

# Binary Search - Recurrence Analysis
# T(n) = T(n/2) + O(1)

def binary_search(arr, target, left=0, right=None):
    """
    Binary Search: T(n) = T(n/2) + O(1)
    - Searches one half: T(n/2)
    - Comparison work: O(1)
    """
    if right is None:
        right = len(arr) - 1
    
    if left > right:
        return -1
    
    mid = (left + right) // 2
    print(f"Checking index {mid}, value = {arr[mid]}")
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # T(n/2)
    else:
        return binary_search(arr, target, left, mid - 1)   # T(n/2)

# Test
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 13

print(f"Searching for {target} in {arr}\n")
result = binary_search(arr, target)

if result != -1:
    print(f"\n✅ Found {target} at index {result}")
else:
    print(f"\n❌ {target} not found")

print("\n📊 Recurrence Relation:")
print("T(n) = T(n/2) + O(1)")
print("\nUsing Master Theorem:")
print("a = 1 (one subproblem)")
print("b = 2 (size is n/2)")
print("f(n) = O(1) (constant work)")
print("\nResult: T(n) = O(log n)")

Output

Click Run to execute your code

Binary Search Pattern:

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

T(n/2) = Search one half
+ 1 = Compare middle element (constant work)
Result: O(log n) - very fast!

Step 3: The Master Theorem (The Shortcut!)

Drawing trees is great for understanding, but there's a faster way! The Master Theorem is like a calculator for these patterns.

The Master Theorem - Simple Version

For patterns like: T(n) = a × T(n/b) + work

Ask one question: "Which part dominates - the recursion or the work?"

The Three Cases (Simplified)

Case 1: Recursion Dominates

When: You split into MANY subproblems (a is large)

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

Result: The splitting dominates → O(n²)

Case 2: Balanced (Most Common!)

When: Recursion and work are balanced

Examples:

Merge Sort: T(n) = 2T(n/2) + n → O(n log n)
Binary Search: T(n) = T(n/2) + 1 → O(log n)

Result: Add a log factor → O(work × log n)

Case 3: Work Dominates

When: You do a LOT of work at each level

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

Result: The work dominates → O(n²)

Try It Yourself!

# Master Theorem Calculator
# Determines complexity of divide-and-conquer algorithms

def master_theorem(a, b, k):
    """
    Master Theorem for T(n) = aT(n/b) + O(n^k)
    
    Case 1: If a > b^k  → T(n) = O(n^(log_b(a)))
    Case 2: If a = b^k  → T(n) = O(n^k log n)
    Case 3: If a < b^k  → T(n) = O(n^k)
    """
    import math
    
    log_b_a = math.log(a) / math.log(b)
    
    print(f"Analyzing: T(n) = {a}T(n/{b}) + O(n^{k})")
    print(f"\na = {a} (number of subproblems)")
    print(f"b = {b} (subproblem size divisor)")
    print(f"k = {k} (work exponent)")
    print(f"\nlog_b(a) = log_{b}({a}) = {log_b_a:.2f}")
    print(f"b^k = {b}^{k} = {b**k}")
    
    if a > b**k:
        print(f"\n✅ Case 1: a > b^k ({a} > {b**k})")
        print(f"Result: T(n) = O(n^{log_b_a:.2f})")
    elif a == b**k:
        print(f"\n✅ Case 2: a = b^k ({a} = {b**k})")
        print(f"Result: T(n) = O(n^{k} log n)")
    else:
        print(f"\n✅ Case 3: a < b^k ({a} < {b**k})")
        print(f"Result: T(n) = O(n^{k})")

# Example 1: Merge Sort
print("=" * 50)
print("Example 1: Merge Sort")
print("=" * 50)
master_theorem(a=2, b=2, k=1)  # T(n) = 2T(n/2) + O(n)

print("\n" + "=" * 50)
print("Example 2: Binary Search")
print("=" * 50)
master_theorem(a=1, b=2, k=0)  # T(n) = T(n/2) + O(1)

print("\n" + "=" * 50)
print("Example 3: Karatsuba Multiplication")
print("=" * 50)
master_theorem(a=3, b=2, k=1)  # T(n) = 3T(n/2) + O(n)

Output

Click Run to execute your code

Quick Quiz: Classify These

Use the three cases to identify the complexity and why.

T(n) = 3T(n/3) + n

Show answer
Balanced: O(n log n) because n^{log_3 3} = n and the extra work matches → add a log factor.
T(n) = 4T(n/2) + n

Show answer
Recursion dominates: O(n²) since n^{log_2 4} = n^2 and n is smaller → total is Θ(n^2).
T(n) = T(n/2) + log n

Show answer
Slightly more than constant extra work per level → O((log n)^2) using the extended Master Theorem intuition.

Common Algorithms

Here are the patterns you'll see most often:

Algorithm	Pattern	Complexity	Why?
Binary Search	T(n) = T(n/2) + 1	O(log n)	Search one half, constant work
Merge Sort	T(n) = 2T(n/2) + n	O(n log n)	Sort both halves, merge takes n
Quick Sort (avg)	T(n) = 2T(n/2) + n	O(n log n)	Same as merge sort on average
Tree Traversal	T(n) = 2T(n/2) + 1	O(n)	Visit every node once

See Merge Sort in Action

# Analyzing Recursive Algorithms
# Example: Merge Sort - Divide and Conquer

def merge_sort(arr):
    """
    Merge Sort: T(n) = 2T(n/2) + O(n)
    - Divides array into 2 halves: 2T(n/2)
    - Merges them back: O(n)
    """
    if len(arr) <= 1:
        return arr
    
    # Divide
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # T(n/2)
    right = merge_sort(arr[mid:])  # T(n/2)
    
    # Conquer (merge)
    return merge(left, right)      # O(n)

def merge(left, right):
    """Merge two sorted arrays - O(n) time"""
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Test
arr = [64, 34, 25, 12, 22, 11, 90]
print("Original:", arr)
sorted_arr = merge_sort(arr)
print("Sorted:", sorted_arr)

print("\n📊 Recurrence Relation:")
print("T(n) = 2T(n/2) + O(n)")
print("\nUsing Master Theorem:")
print("a = 2 (two subproblems)")
print("b = 2 (each is n/2)")
print("f(n) = O(n) (merge work)")
print("\nResult: T(n) = O(n log n)")

Output

Click Run to execute your code

When Master Theorem Doesn't Work

Important: Master Theorem only works when you divide by a constant (like n/2, n/3).

❌ Fibonacci: T(n) = T(n-1) + T(n-2)

Why it doesn't work: Subtracting 1, not dividing by 2

What to do: Draw the tree - you'll see it's O(2ⁿ) - exponential!

Pro Tip: When Master Theorem doesn't apply, draw the recursion tree and count levels manually. It always works!

Summary: The 3-Step Method

To Analyze Any Recursive Algorithm:

Draw the recursion tree - Visualize how it breaks down
Count work per level - Usually it's the same at each level
Apply Master Theorem - Or count levels if it doesn't apply

Interview ready: If someone asks "How do you know?" you can show the recursion tree or write the recurrence to justify it.

Most Common Results:

Binary Search: O(log n) - super fast!
Merge Sort: O(n log n) - efficient sorting
Tree Traversal: O(n) - visit each node once

What's Next?

🎉 Congratulations! You've completed Module 1: Introduction & Fundamentals!

You Now Know:

✅ Why DSA matters for your career
✅ Big O notation and complexity analysis
✅ How to analyze recursive algorithms

You're ready for practical algorithms!

Next up: Module 2: Arrays & Strings where you'll learn powerful techniques like two pointers, sliding window, and solve real interview problems!

Practice Tip: Next time you see a recursive algorithm, try drawing its tree. You'll be amazed how much clearer it becomes!

Previous Time & Space Complexity

Next Array Fundamentals

💼 The Google Interview Question

Merge Sort Recursion Tree (n=8)

The Challenge: Analyzing Merge Sort

🤔 The Problem

Step 1: Draw the Recursion Tree

💡 What You're Seeing

Counting Operations by Hand

Step 2: Writing the Pattern (Recurrence Relation)

For Merge Sort:

Example: Binary Search

Binary Search Pattern:

Step 3: The Master Theorem (The Shortcut!)

The Master Theorem - Simple Version

The Three Cases (Simplified)

Case 1: Recursion Dominates

Case 2: Balanced (Most Common!)

Case 3: Work Dominates

Try It Yourself!

Quick Quiz: Classify These

Common Algorithms

See Merge Sort in Action

When Master Theorem Doesn't Work

❌ Fibonacci: T(n) = T(n-1) + T(n-2)

Summary: The 3-Step Method

To Analyze Any Recursive Algorithm:

What's Next?

You Now Know:

Enjoying these tutorials?