Analyzing Recursive Algorithm Complexity — Master Theorem, Recursion Tree, Substitution

To analyze a recursive algorithm, write a recurrence that expresses its running time on size n in terms of sub-problems, then solve it.

Three standard techniques

1. Substitution method

• Guess a bound
• Prove by induction
• Used when you already suspect the answer

2. Recursion tree

• Draw the tree of recursive calls
• Compute work at each level
• Sum up
• Intuitive and general — works for most recurrences

3. Master theorem

• Plug-and-play formula for T(n) = aT(n/b) + f(n) form
• a = number of sub-problems
• n/b = size of each sub-problem
• f(n) = non-recursive work per call

Master theorem — three cases

• Compute c = log_b(a)
• Case 1: f(n) polynomially smaller than n^c → T(n) = Θ(n^c). Leaves dominate.
• Case 2: f(n) = Θ(n^c) → T(n) = Θ(n^c log n). Balanced.
• Case 3: f(n) polynomially bigger than n^c → T(n) = Θ(f(n)). Root dominates.

Classic examples

Merge sort: T(n) = 2T(n/2) + O(n)

• a=2, b=2, c = log_2(2) = 1
• f(n) = n = Θ(n^1) → Case 2
• T(n) = O(n log n)

Binary search: T(n) = T(n/2) + O(1)

• a=1, b=2, c = 0
• f(n) = 1 = Θ(n^0) → Case 2
• T(n) = O(log n)

Strassen's matrix multiply: T(n) = 7T(n/2) + O(n²)

• a=7, b=2, c ≈ 2.807
• f(n) = n² is polynomially smaller than n^2.807 → Case 1
• T(n) = O(n^2.807) — beats naive O(n³)

Karatsuba multiplication: T(n) = 3T(n/2) + O(n)

• a=3, b=2, c ≈ 1.585
• Case 1 → T(n) = O(n^1.585) — beats naive O(n²)

Naive Fibonacci — NOT master theorem form

• T(n) = T(n-1) + T(n-2) + O(1)
• Sub-problems shrink by additive constant, not multiplicative factor
• Use recursion tree: branches into 2 per level, depth n
• T(n) = O(2^n), more tightly O(φ^n) ≈ O(1.618^n)
• Memoization reduces to O(n)
• Matrix exponentiation: O(log n)

Recursion tree — when master theorem doesn't apply

Draw the tree:

• Merge sort: log n levels, O(n) work per level → O(n log n)
• Binary search: log n levels, O(1) per level → O(log n)
• Fibonacci: n levels, branches doubling → O(2^n)
• Linear recursion T(n) = T(n-1) + O(1): n levels, O(1) each → O(n)

Memorize these common recurrences

• T(n) = T(n-1) + O(1) → O(n)
• T(n) = T(n-1) + O(n) → O(n²)
• T(n) = T(n/2) + O(1) → O(log n)
• T(n) = T(n/2) + O(n) → O(n)
• T(n) = 2T(n/2) + O(1) → O(n)
• T(n) = 2T(n/2) + O(n) → O(n log n)
• T(n) = 2T(n-1) + O(1) → O(2^n) (Tower of Hanoi)
• T(n) = T(n-1) + T(n-2) + O(1) → O(φ^n)

Memoization converts exponential to polynomial

• Naive Fib: O(2^n) due to overlapping sub-problems
• Memoized Fib: O(n) — each sub-problem computed once
• Tabulated Fib with rolling vars: O(n) time, O(1) space
• This is the heart of dynamic programming

Space complexity — don't forget the stack

• Merge sort: O(n) aux + O(log n) stack = O(n)
• Binary search: O(log n) stack
• Naive Fib: O(n) stack
• Quicksort: O(log n) avg, O(n) worst
• Tail recursion: Java does NOT optimize — stack still grows
• For deep recursion, convert to iterative to avoid StackOverflowError

Common traps

1. Applying master theorem to non-master form

• Fibonacci — use recursion tree
• Tower of Hanoi — use recursion tree

2. Forgetting the regularity condition in Case 3

• a·f(n/b) ≤ k·f(n) for some k < 1
• Usually holds for polynomials

3. Confusing log base

• log_b(a) — log of a base b
• Don't confuse with log n (which is base 2 by convention in CS)

4. Forgetting space complexity

• Recursion always uses O(depth) stack space
• Can cause StackOverflow even if time is fine

Recommendation: When given a recursive algorithm, write the recurrence first — identify a (number of sub-problems), b (shrinkage factor), and f(n) (non-recursive work). If the form is T(n) = aT(n/b) + f(n), apply master theorem with c = log_b(a) and the three cases. If not (like Fibonacci or Tower of Hanoi), use the recursion tree — draw the levels, compute work per level, sum up. Memorize the common recurrences — merge sort's O(n log n), binary search's O(log n), Fibonacci's O(2^n) — these appear constantly. When you see an exponential recurrence with overlapping sub-problems, reach for memoization to convert to polynomial — this is the essence of dynamic programming. Always compute space complexity too: recursion is O(depth) stack space, and Java does not optimize tail calls — deep recursion can StackOverflow. For interviews, practice deriving the recurrence from the code in one pass: read the function, count sub-calls, count non-recursive work, write the recurrence, apply master theorem. The most common mistake is trying to force master theorem onto non-master-form recurrences; when in doubt, draw the tree.