Recursive Sum: Recurrence Relations

Recurrence Relations: Recursive Sum Example video (25 minutes) (Spring 2021)

Motivation

Recurrence relations can aid in determining Big-O complexity of recursive functions. A recurrence relation is a relationship in which a function T(...) occurs on both sides of the = sign. For example, T(n) = 1 + T(n / 2).

General steps for solving a recurrence relation

Understand what the recursive algorithm is actually doing, and identify base case(s). Identify general recursive case. Identify how the input shrinks as progress is made towards the base case.
Formalize the recurrence relation. Express the base case(s) and general case in T(n) notation, or running time syntax. (See below example)
Iterate/expand a few times, plugging in shrinking values of n. Simplify the resulting expression.
Spot a pattern that emerges, which can be express in terms of "k", the number of iterations taking place.
Write the recurrence relation in terms of k
Identify a value of k, given how k and n interact in the relation, such that a base case with a known value can substituted into the relation.
Finally, solve the relation using the known values.

Recursive sum example

template <typename RandomAccessIt>
long recursive_sum(RandomAccessIt begin, RandomAccessIt end)
{
    if (begin == end) {
        return 0;
    } else if (end - begin == 1) {
        return *begin;
    } else {
        RandomAccessIt middle = begin + ((end - begin) / 2);
        return recursive_sum(begin, middle) + recursive_sum(middle, end);
    }
}

1. Understand, identify base/general cases

This function recursively calculates the sum of a collection of values in the range between two iterators, [begin, end)

The base case of an empty range, begin == end, simply returns 0.

Returning 0 is a constant time operation.

So T(0) = 1.

The base case of a single element dereferences the iterator to access its value and returns it.

Dereferencing an iterator and returning the value is a constant time operation

So T(1) = 1.

The general recursive case calculates a middle iterator position, then makes 2 recursive calls on ranges half the size of the original range.

The iterator calculation is a constant time operation.

The two recursive calls have running time linked to a size that is half that of the original range.

So T(n) = 1 + 2T(n / 2).

2. Formalize recurrence relation

We now have our base cases and general recursive case:

Base: T(0) = 1

Base: T(1) = 1

General: T(n) = 1 + 2T(n / 2)

3. Iterate/expand/simplify the general case relation

T(n) = 1 + 2T(n / 2)
T(n) = 1 + 2(1 + 2T((n / 2) / 2))
T(n) = 1 + 2 + 4T(n / 4)
T(n) = 3 + 4T(n / 4)
T(n) = 3 + 4(1 + 2T((n / 4) / 2))
T(n) = 3 + 4 + 8T(n / 8)
T(n) = 7 + 8T(n / 8)
T(n) = 7 + 8(1 + 2T((n / 8) / 2))
T(n) = 7 + 8 + 16T(n / 16)
T(n) = 15 + 16T(n / 16)

4. Spot a pattern, in terms of "k" iterations

There is a useful "Sum of Powers of 2" to be aware of for this step

1   + 2   + 4   + 8   + ... + 2^k = 2^(k + 1) - 1
2^0 + 2^1 + 2^2 + 2^3 + ... + 2^k = 2^(k + 1) - 1

2^0                         = 2^(0 + 1) - 1 = 1
2^0 + 2^1                   = 2^(1 + 1) - 1 = 3
2^0 + 2^1 + 2^2             = 2^(2 + 1) - 1 = 7
2^0 + 2^1 + 2^2 + 2^3       = 2^(3 + 1) - 1 = 15
2^0 + 2^1 + 2^2 + 2^3 + 2^4 = 2^(4 + 1) - 1 = 31

In this relation, the leading term seems to be growing from 1 to 3 to 7 in a "sum of powers of 2" manner, or 2^k - 1.

The multiple of T, and denominator below n, both seem to be growing from 2 to 4 to 8 in a 2^k manner.

5. Write the relation in terms of k

T(n) = (2^k) - 1 + (2^k)T(n / (2^k))

(To double check this, you can expand this relation in a similar way to step 3. The goal would be to observe k+1 in each location where k is, after one expansion).

6. Identify a k value that allows substitution of a base case

We know that T(1) = 1. So what value of k will let us substitute in T(1) to this relation?

We want to rewrite T(n / (2^k)) as T(1), so we solve n / (2^k) = 1:

n / (2^k) = 1
n = (2^k)
log2(n) = k

7. Solve using known values

Substituting in log2(n) for k ...

T(n) = (2^(log2(n))) - 1 + (2^(log2(n)))*T(1)
(Exponential Identity: 2^(log2(n)) = n)
T(n) = n - 1 + n * T(1)
T(n) = n - 1 + n * 1
T(n) = 2n - 1
O(T(n)) = O(2n - 1)
O(T(n)) = O(n)

Hopefully this is intuitive: to calculate the sum of elements in a range having size n, we would have to access and add each of the elements once.

Thanks

Thanks to Brian Foster for writing up the initial draft of these notes.