Writing Recurrence Relations

Time defined in terms of itself

A recursive algorithm's running time is naturally described by a recurrence: T(n) expressed using T on smaller inputs plus the work done at the current level. Factorial or summing a list recursively makes one call on n − 1 and does constant work: T(n) = T(n − 1) + O(1), which unrolls to O(n). Binary search makes one call on half the input: T(n) = T(n/2) + O(1), giving O(log n). Merge sort makes two calls on halves and merges in linear time: T(n) = 2T(n/2) + O(n), giving O(n log n). A function that makes two calls on n − 1, such as naive Fibonacci, gives T(n) = T(n − 1) + T(n − 2) + O(1), which grows exponentially. Solve simple recurrences by unrolling (substituting repeatedly until a pattern appears), by a recursion tree, by the master theorem for divide-and-conquer forms, or by guessing and proving with induction (the substitution method).

Unrolling a recurrence

Each substitution exposes one more level until the base case is reached.

Recurrences for three classic functions

The recurrence follows directly from the number and size of the recursive calls.

def total(a, i=0):
    if i == len(a):
        return 0
    return a[i] + total(a, i + 1)
# T(n) = T(n-1) + O(1)  ->  O(n)

def bsearch(a, t, lo, hi):
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if a[mid] == t:
        return mid
    return bsearch(a, t, mid + 1, hi) if a[mid] < t else bsearch(a, t, lo, mid - 1)
# T(n) = T(n/2) + O(1)  ->  O(log n)

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    return merge(left, right)        # O(n) merge
# T(n) = 2T(n/2) + O(n)  ->  O(n log n)

# unrolling T(n) = T(n-1) + c:
# T(n) = T(n-2) + 2c = T(n-3) + 3c = ... = T(0) + n*c  ->  O(n)

Slicing has a cost

In Python, a[:mid] copies elements, costing O(n) time and memory per call. Merge sort pays that anyway in its merge step, but a binary search written with slices becomes O(n) instead of O(log n). Pass indices instead.

त्वरित जाँच: Which recurrence describes binary search?

• T(n) = 2T(n/2) + O(n)
• T(n) = T(n − 1) + O(n)
• T(n) = T(n/2) + O(1)
• T(n) = 2T(n − 1) + O(1)