3.5. Complexity of Simple Recursive Algorithms

In this chapter we will study complexity of the programs that combine both loops and recursion.

3.5.1. Complexity of computing the factorial

Typically, any terminating recursive algorithm works by calling itself on progressively smaller instances of some data structures. For instance, consider the “Hello, World!” of all recursive programs — the factorial function:

let rec factorial n =
  if n <= 0 then 1
  else n * (factorial (n - 1))

Assume its complexity is the number of multiplications (taken as the most expensive operations) it performs for a number n (so n will also serve as the “size” of the problem). We can write the relation on factorial’s complexity \(F(n)\) using the following relation:

\[\begin{split}\begin{align*} F(0) &= 0 \\ F(n) &= F (n - 1) + 1 \end{align*}\end{split}\]

That is, the value of \(F(n)\) is defined recursively (shouldn’t be that much of a surprise, huh?) thourgh the value of \(F(n - 1)\).

3.5.2. Method of differences

We can now exploit this pattern by constructing a number of equations of the following shape, following the definition of \(F(n)\) of the factorial complexity, and sum them up together:

\[\begin{split}\begin{align*} && F(n) &- F (n - 1) &= 1 \\ &+& F(n - 1) &- F (n - 2) &= 1 \\ &+& F(n - 2) &- F (n - 3) &= 1 \\ &+& \ldots \\ &+& F(1) &- F(0) &= 1 \\ \hline && F(n) &- F(0) &= n \end{align*}\end{split}\]

As the result, we obtain \(F(n) = n\) (since \(F(0) = 0\)), therefore we can conclude that \(F(n) \in O(n)\).

3.5.3. Recurrence relations

What we’ve seen as an example of the factorial complexity can be generalised to the following definition of a recurrence relation.

Definition

Recurrence relation for a function \(f\) is an equation that expresses the value \(f(n)\) through the values \(f(n-1), \ldots, f(0)\).

Naturally, recurrence relations are a method to express complexities of recursive algorithms depending on input sizes of the recursive call, and we’ve just seen an example of such for the factorial, namely \(F(n) = F(n - 1) + 1\). Similarly to well-founded recursion and induction, recurrence relations require initial values to “bootstrap” the computation (for instance, \(F(0) = 0\)).

The main challenge that comes with recurrence relations is to find explicit (non-recurrent) expression of \(f\) (aka closed form) as a function of its argument \(n\) (e.g., \(F(n) = n\)). This is similar to finding an explicit value for a sum in the case of loops.

3.5.4. First-order recurrence relations

Most of the time we will be considering the following special case of recurrence relations.

Definition

First-order recurrence relation for a function \(f\) is an equation that expresses the value \(f(n)\) recursively only via the value of \(f(n-1)\), when \(n > a\) for some \(a\).

Example

For some \(c > 0\):

\[\begin{split}\begin{align*} f(0) &= 1 \\ f(n) &= c \cdot f (n - 1) \end{align*}\end{split}\]

By inspection and unfolding the definition of \(f(n)\), we get the solution \(f(n) = c^n\).

Definition

Homogeneous recurrence relations take the following form for some constants \(a\), \(f(n)\) and a coefficient \(b_n\), which might be a function of \(n\):

\[\begin{split}\begin{align*} f(n) &= b_n \cdot f(n - 1) ~\text{if}~ n > a \\ f(a) &= d \end{align*}\end{split}\]

By unfolding the definition recursively, we can obtain the following formula to solve it:

\[\begin{split}\begin{align*} f(n) &= b_n \cdot f(n - 1) \\ &= b_n \cdot b_{n-1} \cdot f(n - 2) \\ & \ldots \\ &= b_n \cdot b_{n - 1} \cdot \ldots \cdot b_{a + 1} \cdot f(a) \\ &= b_n \cdot b_{n - 1} \cdot \ldots \cdot b_{a + 1} \cdot d \end{align*}\end{split}\]

Therefore:

\[f(n) = \left( \prod_{i = a + 1}^{n}b_i \right) \cdot f(a)\]

You can try to remember that formula, but it’s easier to remember how it is obtained.

3.5.5. Inhomogeneous recurrence relations

Definition

Inhomogeneous recurrence relations take the following form for some constants \(a\), \(f(n)\) and a coefficient \(b_n\) and \(c_n\), which might be functions of \(n\):

\[\begin{split}\begin{align*} f(n) &= b_n \cdot f(n - 1) + c_n ~\text{if}~ n > a \\ f(a) &= d \end{align*}\end{split}\]

The trick to solve an inhomogeneous relation is to “pretend” that we are solving a homogeneous recurrence relation by changing the function \(f(n)\) to \(g(n)\), such that

\[\begin{split}\begin{align*} f(n) &= b_{a+1}\cdot \ldots \cdot b_n \cdot g(n) ~\text{if}~ n > a \\ f(a) &= g(a) = d \end{align*}\end{split}\]

Intuitively, this “change of function” allows us to reduce a general recurrence relation to the one where \(b_n = 1\). In other words, \(g(n)\) is a “calibrated” version of \(f(n)\) that behaves “like” \(f(n)\) module the appended product of coefficients.

Let us see how this trick helps us to solve the initial relation. We start by expanding the definition of \(f(n)\) for \(n > 0\) as follows:

\[f(n) = b_n \cdot f(n - 1) + c_n\]

We then recall that \(f(n)\) can be expressed via \(g(n)\), and rewrite both parts of this equation as follows:

\[\underbrace{b_{a+1}\cdot \ldots \cdot b_n}_{X} \cdot g(n) = \underbrace{b_n \cdot b_{a+1}\cdot \ldots \cdot b_{n-1}}_{X} \cdot g(n - 1) + c_n\]

Notice that the parts marked via \(X\) are, in fact the same, so we can divide both parts of the expression by it, so we can get

\[g(n) = g(n - 1) + d_n ~\text{where}~ d_n = \frac{c_n}{\prod_{i = a + 1}^{n}b_i}.\]

We can now solve the recurrence on \(g(n)\) via the method of difference, obtaining

\[g(n) = g(a) + \sum_{j = a + 1}^{n}d_j ~\text{where}~ d_j = \frac{c_j}{\prod_{k = a + 1}^{j}b_k}\]

The final step is to obtain \(f(n)\) by multiplying \(g(n)\) by the corresponding product. This way we obtain:

\[f(n) = \prod_{i = a + 1}^{n} b_i \cdot \left(g(a) + \sum_{j = a + 1}^{n}d_j\right) ~\text{where}~ d_j = \frac{c_j}{\prod_{k = a + 1}^{j}b_k}\]

As in the previous case, it is much easier to remember the “trick” with introducing \(g(n)\) and reproduce it every time you solve a relation, than to remember that formula above! In the examples we’ll, the initial index \(a\) will be normally be 0 or 1. The techniques for series summation and approximation will come useful when dealing with coefficients \(d_j\).

Example

Consider the following recurrence relation:

\[\begin{split}\begin{align*} f(n) &= 3 \cdot f(n - 1) + 1 ~\text{if}~ n > 0 \\ f(0) &= 0 \end{align*}\end{split}\]

We start by changing the function so \(f(n) = 3^n \cdot g(n)\) for an unknown \(g(n)\), since \(b_i = 3\) for any \(i\). Substityting for \(f(n)\) gives us

\[g(n) = g(n - 1) + \frac{1}{3^n}\]

By method of differences, we obtain

\[g(n) = \sum_{i = 1}^{n}\frac{1}{3^i} = \left[\sum_{i = 1}^{n}\frac{1}{a^i}\right]_{a = \frac{1}{3}} = \left[\frac{a (1 - a^n)}{1-a}\right]_{a = \frac{1}{3}} = \frac{1}{2}\left(1 - \frac{1}{3^n}\right)\]

Finally, restoring \(f(n)\), we get

\[f(n) = 3^n \cdot g(n) = \frac{3^n}{2}\left(1 - \frac{1}{3^n}\right) = \frac{1}{2} \left(3^n - 1\right) \in O(3^n)\]