Recurrence Relations

Recurrence

For a recursive algorithm, we cannot directly calculate time complexity simply by counting how many times each statement executes. Instead, we can form a recurrence relation and solve it through iterative expansion.

Summation

int sum(int n) {
    if (n <= 0) {
        return 0;
    }
    return sum(n - 1) + n;
}

Insertion sort

void insertion_sort(int arr[], int n) {
    if (n <= 1) {
        return;
    }
    insertion_sort(arr, n - 1);
    int last = arr[n - 1];
    int j = n - 2;
    while (j >= 0 && arr[j] > last) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = last;
}

Tower of Hanoi

There are three towers, A, B, and C. Tower A holds $n$ disks stacked from largest at the bottom to smallest at the top. The goal is to move all disks from A to C. Only one disk may move at a time, and a larger disk may never be placed on a smaller one.

A recursive algorithm solves the Tower of Hanoi in three stages:

1. Move the first $n-1$ disks from A to B, using C as the helper.
2. Move the final, largest disk directly from A to C.
3. Move the $n-1$ disks from B to C, using A as the helper.

void hanoi(int n, char A, char B, char C) {
    if (n == 1) {
        move(1, A, C);
    } else {
        hanoi(n - 1, A, C, B);
        move(n, A, C);
        hanoi(n - 1, B, A, C);
    }
}

If each move takes one second, solving a 64-disk Tower of Hanoi would take about 580 billion years.