Write the Recurrence From the Code

A recurrence is an equation that gives an algorithm's running time on an input of size n in terms of its running time on smaller inputs. For divide and conquer it takes the form T(n) = a·T(n/b) + f(n): a recursive calls, each on an input of size n/b, plus f(n), the work one call does outside them in its divide and combine steps. This card reads that equation off three functions, binary search, the largest value by halves, and merge sort.

Three questions give the three parts. How many recursive calls does one call make, counting only those that actually run? How large is the input to each? What does the call do besides recurse? The base case costs a constant, written T(1) = O(1), and is usually left unwritten. When n is odd the halves are one item apart in size, which never changes the answer, so they are written n/2.

def binary_search(items: list[int], target: int, low: int, high: int) -> int:
    if low > high:
        return -1
    mid = (low + high) // 2
    if items[mid] == target:
        return mid
    if items[mid] < target:
        return binary_search(items, target, mid + 1, high)
    return binary_search(items, target, low, mid - 1)

def largest(items: list[int], low: int, high: int) -> int:
    if low == high:
        return items[low]
    mid = (low + high) // 2
    left = largest(items, low, mid)
    right = largest(items, mid + 1, high)
    return left if left >= right else right

def merge_sort(items: list[int]) -> list[int]:
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)

The three functions were run in a container on test inputs before being copied here, with merge written out: binary search found 11 at index 5 of 1 3 5 7 9 11 13 15 and returned −1 for 4, and the other two returned 9 and 1 2 3 5 6 7 8 9 for 7 3 9 1 6 8 2 5.

Two slips account for most wrong recurrences. Counting one call where there are two, T(n) = T(n/2) + O(n) for merge sort, drops half the work. Writing the size as n − 1 where it is n/2, as in T(n) = 2T(n − 1) + O(1), describes a function that shrinks by one item per call and makes about 2ⁿ calls. Count the calls that run, and read the size from the arguments.

The recurrence is not yet the cost. It says the same thing as the code in a form that can be solved, and solving it is the next step: by drawing the calls level by level, or by the master theorem's shortcut.