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

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.