Recurrence Relations and Recursive Algorithm Complexity

What Is a Recurrence Relation?

A recurrence relation expresses the time complexity $T(n)$ of a recursive algorithm in terms of the time complexity of its sub-calls.

KEY TAKEAWAY: Recurrence relations are the natural language for analysing recursive algorithms. They describe: (1) the work done at the current level, and (2) the work delegated to recursive calls.

General Form

$$T(n) = a \cdot T!\left(\frac{n}{b}\right) + f(n)$$

Where:
- $a$ = number of recursive sub-calls
- $n/b$ = size of each sub-call (input is divided by $b$)
- $f(n)$ = work done outside the recursive calls (divide + merge steps)
- $T(1)$ = base case cost (usually $O(1)$)

Writing a Recurrence Relation

Step 1: Identify the base case
Step 2: Count recursive sub-calls ($a$)
Step 3: Determine how input is divided ($b$)
Step 4: Measure non-recursive work at each level ($f(n)$)

Example 1: Mergesort

ALGORITHM MergeSort(A, n)
    if n = 1 then return A   // base case
    left ← MergeSort(A[0..n/2], n/2)    // 1 call on n/2 elements
    right ← MergeSort(A[n/2..n], n/2)   // 1 call on n/2 elements
    return Merge(left, right)             // O(n) merge step

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

Example 2: Binary Search

ALGORITHM BinarySearch(A, target, low, high)
    if low > high then return -1
    mid ← (low + high) / 2
    if A[mid] = target then return mid
    if target < A[mid] then
        return BinarySearch(A, target, low, mid - 1)   // 1 call on n/2
    else
        return BinarySearch(A, target, mid + 1, high)  // 1 call on n/2

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

Example 3: Naive Recursive Fibonacci

FUNCTION Fibonacci(n)
    if n <= 1 then return n
    return Fibonacci(n-1) + Fibonacci(n-2)

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

This does not fit the standard Master Theorem form — solving it gives $T(n) = O(2^n)$ (exponential — very bad!).

Solving Recurrences by Unrolling

For simple recurrences, unroll and find a pattern:

$T(n) = T(n/2) + c$ (Binary Search)

$T(n) = T(n/2) + c$
$= T(n/4) + c + c$
$= T(n/8) + 3c$
$= T(n/2^k) + kc$

When $n/2^k = 1$, i.e., $k = \log_2 n$:
$T(n) = T(1) + c \log_2 n = O(\log n)$ ✓

Recurrences Not in Master Theorem Form

Some recurrences (like Fibonacci’s $T(n) = T(n-1) + T(n-2)$) are decreasing, not dividing. For these:
- The input decreases by a constant each call (not a factor)
- May result in $O(2^n)$ or $O(n^2)$ depending on structure
- Often indicate that dynamic programming is needed

EXAM TIP: Be able to write the recurrence relation for a given recursive algorithm and identify the values of $a$, $b$, and $f(n)$. You do not need to solve arbitrary recurrences — only those solvable by the Master Theorem or simple unrolling.