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:
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:
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\):
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\):
By unfolding the definition recursively, we can obtain the following formula to solve it:
Therefore:
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\):
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
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:
We then recall that \(f(n)\) can be expressed via \(g(n)\), and rewrite both parts of this equation as follows:
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
We can now solve the recurrence on \(g(n)\) via the method of difference, obtaining
The final step is to obtain \(f(n)\) by multiplying \(g(n)\) by the corresponding product. This way we obtain:
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:
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
By method of differences, we obtain
Finally, restoring \(f(n)\), we get