Ph.D. Qual Study Assistant: Recursive Complexity

Understanding Recursion

A recursive algorithm is one that solves a problem by calling itself with smaller instances of the same problem. This process continues until it reaches a "base case," which is simple enough to be solved directly without further recursion. To analyze its complexity, we first need to express its runtime as a recurrence relation.

function factorial(n) {
  if (n <= 1) { // Base Case
    return 1;
  } else { // Recursive Step
    return n * factorial(n - 1);
  }
}

The recurrence for this would be `T(n) = T(n-1) + O(1)`, as it makes one call to a subproblem of size `n-1` and performs constant-time work (multiplication).

Methods for Solving Recurrences

Substitution Method

A formal method where you guess the form of the solution (e.g., O(n log n)) and then use mathematical induction to prove that your guess is correct.

Recursion Tree Method

A visual and intuitive method. You draw out the recursive calls as a tree and sum up the work done at each level to find the overall complexity.

Master Theorem

A powerful "shortcut" for solving recurrences of the form `T(n) = aT(n/b) + f(n)`. See our dedicated guide!

Recursion Tree Examples

Simple Example: Linear Recursion

Let's analyze `T(n) = T(n-1) + c` (like the factorial example).

This "chain" of recursion has `n` levels, and each level does constant work `c`. The total work is the sum of work at all levels, resulting in `O(n)` complexity.

Medium Example: Merge Sort

Let's analyze `T(n) = 2T(n/2) + cn` (the recurrence for Mergesort).

The work is balanced across the tree. Summing the work at each level (`cn`) for the total number of levels (`log n`) gives `O(n log n)`.

Advanced Example: A Root-Heavy Tree

Let's analyze `T(n) = 3T(n/4) + cn²`.

Here, the amount of work done at each level decreases rapidly. The total work is dominated by the work at the root node, `cn²`. This leads to a complexity of `O(n²)`.

Practice: Write the Recurrence

1. Binary Search: Identify the components of its recurrence relation `T(n) = aT(n/b) + f(n)`.

function binarySearch(arr, target, low, high) {
  if (low > high) return -1; // Base Case
  
  let mid = Math.floor((low + high) / 2); // O(1) work

  if (arr[mid] === target) {
    return mid;
  } else if (arr[mid] > target) {
    return binarySearch(arr, target, low, mid - 1); // One recursive call on ~n/2
  } else {
    return binarySearch(arr, target, mid + 1, high); // One recursive call on ~n/2
  }
}

a =

b =

f(n) =

2. Recursive Sum: Identify the recurrence for this function.

function recursiveSum(arr, n) {
  if (n <= 0) return 0; // Base Case
  let sum = recursiveSum(arr, n - 1); // One recursive call on n-1
  for (let i = 0; i < n; i++) { // O(n) work
    sum += arr[i];
  }
  return sum;
}

a =

b =

f(n) =

3. A Root-Heavy Function: Identify the recurrence for this function.

function rootHeavy(n) {
  if (n <= 1) return; // Base Case

  rootHeavy(n / 2); // One recursive call on n/2

  for (let i = 0; i < n; i++) { // O(n) work
    // some constant time operation...
  }
}

a =

b =

f(n) =