Analyzing Recursive Complexity (Recurrences)

Analyzing recursive code means writing a recurrence — an equation that expresses a function’s cost in terms of its cost on smaller inputs — and then solving it for Big-O. The three tools you need are: writing the recurrence, drawing a recursion tree to add up the work per level, and the Master Theorem as a shortcut for divide-and-conquer. This page builds all three gently.

Step 1: write the recurrence

For a recursive function, ask two questions: how much work does one call do outside its recursive calls, and how many recursive calls on what size? Write T(n) = (calls) · T(smaller) + (work per call).

Linear recursion that shrinks n by 1 and does O(1) work per call gives T(n) = T(n-1) + O(1), which unrolls to O(n):

long long factorial(int n) {
    if (n <= 1) return 1;        // base case
    return (long long)n * factorial(n - 1); // T(n) = T(n-1) + O(1)
}

long factorial(int n) {
    if (n <= 1) return 1;        // base case
    return (long) n * factorial(n - 1); // T(n) = T(n-1) + O(1)
}

function factorial(n) {
  if (n <= 1) return 1;          // base case
  return n * factorial(n - 1);   // T(n) = T(n-1) + O(1)
}

def factorial(n):
    if n <= 1:                    # base case
        return 1
    return n * factorial(n - 1)   # T(n) = T(n-1) + O(1)

There are n calls, each O(1), so the time is O(n). Space is O(n) too — the call stack holds n frames at its deepest.

Step 2: the recursion tree

A recursion tree draws every call as a node and sums the work level by level. It’s the most reliable way to handle branching recursion. Take naive Fibonacci, which makes two calls each step — T(n) = T(n-1) + T(n-2) + O(1):

long long fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2); // two branches
}

long fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2); // two branches
}

function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2); // two branches
}

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)  # two branches

The tree roughly doubles in width each level and is about n levels deep, so the total number of nodes is about 2ⁿ. That makes naive Fibonacci O(2ⁿ) — exponential and unusable beyond small n. Adding memoization caches each fib(k) once, collapsing it to O(n).

For beginners: “How many calls, and how much smaller each time?” answers most questions. One call, size n-1 → linear. Two calls, size n-1 → exponential. Two calls, size n/2 → that’s the divide-and-conquer case below.

Step 3: divide-and-conquer and the Master Theorem

Divide-and-conquer algorithms split the input into a pieces of size n/b and do O(n^d) work to combine. Their recurrence is:

T(n) = a · T(n / b) + O(n^d)

The Master Theorem reads off the answer by comparing d against log_b(a):

Case	Condition	Result
1	d < log_b(a)	T(n) = O(n^(log_b a))
2	d = log_b(a)	T(n) = O(n^d · log n)
3	d > log_b(a)	T(n) = O(n^d)

The intuition: case 1 means the leaves dominate, case 3 means the top-level work dominates, and case 2 is the balanced tie where every level costs the same — so you pay O(n^d) across log n levels.

Applying it to merge sort

Merge sort splits in half (a = 2, b = 2) and merges in linear time (d = 1). Here log₂ 2 = 1 = d, so case 2: T(n) = O(n log n).

#include <vector>
using namespace std;

vector<int> mergeSort(vector<int> a) {
    if (a.size() <= 1) return a;
    int mid = a.size() / 2;
    vector<int> left(a.begin(), a.begin() + mid);
    vector<int> right(a.begin() + mid, a.end());
    left = mergeSort(left);    // T(n/2)
    right = mergeSort(right);  // T(n/2)
    vector<int> out;           // merge: O(n)
    int i = 0, j = 0;
    while (i < (int)left.size() && j < (int)right.size())
        out.push_back(left[i] <= right[j] ? left[i++] : right[j++]);
    while (i < (int)left.size()) out.push_back(left[i++]);
    while (j < (int)right.size()) out.push_back(right[j++]);
    return out;
}

import java.util.*;

int[] mergeSort(int[] a) {
    if (a.length <= 1) return a;
    int mid = a.length / 2;
    int[] left = mergeSort(Arrays.copyOfRange(a, 0, mid));   // T(n/2)
    int[] right = mergeSort(Arrays.copyOfRange(a, mid, a.length)); // T(n/2)
    int[] out = new int[a.length];                            // merge: O(n)
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length)
        out[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    while (i < left.length) out[k++] = left[i++];
    while (j < right.length) out[k++] = right[j++];
    return out;
}

function mergeSort(a) {
  if (a.length <= 1) return a;
  const mid = Math.floor(a.length / 2);
  const left = mergeSort(a.slice(0, mid));   // T(n/2)
  const right = mergeSort(a.slice(mid));     // T(n/2)
  const out = [];                            // merge: O(n)
  let i = 0, j = 0;
  while (i < left.length && j < right.length)
    out.push(left[i] <= right[j] ? left[i++] : right[j++]);
  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);
  return out;
}

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])    # T(n/2)
    right = merge_sort(a[mid:])   # T(n/2)
    out = []                      # merge: O(n)
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out

Binary search is T(n) = T(n/2) + O(1) (a = 1, b = 2, d = 0). Here log₂ 1 = 0 = d → case 2 → O(log n).

Going deeper: The Master Theorem only fits the a·T(n/b) + O(n^d) shape. Recurrences like T(n) = T(n-1) + O(n) (which is O(n²), e.g. naive quicksort’s worst case) don’t divide by a constant factor — solve those with a recursion tree or by unrolling. Also remember space: recursion depth d costs O(d) stack even when the time is small.

Quick reference

Recurrence	Big-O	Example
T(n) = T(n-1) + O(1)	O(n)	factorial
T(n) = T(n-1) + O(n)	O(n²)	quicksort worst case
T(n) = T(n/2) + O(1)	O(log n)	binary search
T(n) = 2T(n/2) + O(n)	O(n log n)	merge sort
T(n) = 2T(n-1) + O(1)	O(2ⁿ)	naive Fibonacci / subsets

Next steps

Compare your recurrence findings against the complexity cheat sheet, revisit time vs space complexity for the stack-space angle, and then test yourself with the complexity exercises.