Solving Recurrence Relations (Part I)

Introduction

In the previous post, we introduced the concept of recurrence relations. In this article and the following two articles, we will learn how to solve the recurrence relations to get the running time of recursive algorithms. Solving the recurrence relation means finding the closed form expression in terms of $n$. There are various techniques available to solve the recurrence relations. Some techniques can be used for all kind of recurrence relations and some are restricted to recurrence relations with a specific format.

Forward substitution method

One of the simplest methods for solving simple recurrence relations is using forward substitution. In this method, we solve the recurrence relation for $n = 0, 1, 2, …$ until we see a pattern. Then we make a guesswork and predict the running time. The final and important step in this method is we need to verify that our guesswork is correct by using the induction. Consider a recurrence relation
$$T(n) = \begin{cases} 1 & \text{ if } n = 1 \\
T(n - 1) + 1 & \text{otherwise}
\end{cases}$$
We can calculate the running time for $n = 0, 1, 2, ..$ as follows

We can easily see the pattern here. When the value of $n = k$, $T(n) = k$. So the running time is
$$T(n) = n$$
We need to verify that the running time we guessed is correct by induction (not mathematical induction ;)). Since $T(n) = n$, we can clearly see that $T(1) = 1, T(2) = 2, T(3) = 3, …$.

Consider another example
$$T(n) = \begin{cases} 1 & \text{ if } n = 1 \ 2T(n - 1) + 1 & \text{otherwise} \end{cases}$$

As above, we can calculate the running time for $n = 0, 1, 2, …,$ as follows

We already started to see the pattern here. When the value of $n$ is $k$ the patter would be
$$T(k) = 2^{k - 1} + 2^{k - 2} + … + 2^0$$
This is a geometric series whose sum can be easily calculated to be $2^k - 1$. Therefore, the running time of the algorithm is,
$$T(n) = 2^n - 1$$
The correctness of this running time can be easily proved by putting $n = 1, 2, 3, …$ in above equation.

Back substitution method

In forward substitution method, we put $n = 0, 1, 2, …$ in the recurrence relation until we see a pattern. In backward substitution, we do the opposite i.e. we put $n = n, n - 1, n - 2, …$ or $n = n, n/2, n/4, …$ until we see the pattern. After we see the pattern, we make a guesswork for the running time and we verify the guesswork. Let us use this method in some examples.

Consider an example recurrence relation given below
$$T(n) = \begin{cases} 1 & \text{ if } n = 1 \\ 2T \left (\frac{n}{2} \right) + n & \text{otherwise} \end{cases}$$

Given $T(n)$, we can calculate the value of $T(n/2)$ from the above recurrence relation as
$$T(n/2) = 2T\left ( \frac{n}{4} \right ) + \frac{n}{2}$$
Now we back substitute the value of $T(n/2)$ in $T(n)$
$$T(n) = 2^2T\left (\frac{n}{2^2}\right ) + 2n$$
We proceed in a similar way
$$\begin{align}T(n) &= 2^3T \left (\frac{n}{2 ^3} \right ) + 3n \\
&= 2^4T \left (\frac{n}{2^4} \right ) + 4n\\
&= 2^kT \left (\frac{n}{2^k} \right ) + kn
\end{align}$$
Now we should use the boundary (base) condition i.e. $T(1) = 1$. In order to use the boundary condition, the entity inside $T()$ must be 1 i.e.
$$\frac{n}{2^k} = 1$$
Taking $\log_2$ on both sides,
$$n = \log_2 n$$
The equation (6) becomes
$$\begin{align}
T(n) &= 2^{\log_2 n}T \left (\frac{n}{2^{\log_2 n}} \right ) + \log_2 n.n \\
& = nT(1) + n\log_2 n \\
& = n\log_2 n + n
\end{align}$$
The correctness of above running time can be proved using induction. Put $n = 2, 4, 8, 16, …$ and you can easily verify that the guessed running time is actually correct.

We rarely use forward and backward substitution method in the practical cases. There are much more sophisticated and fast methods. But these methods can be used as a last resort when other methods are powerless to solve some kinds of recurrences.

Homogeneous recurrences

Some recurrences take the form
$$a_0T(n) + a_1T(n - 1) + … +a_kT(n - k) = 0$$
This recurrence is called Homogeneous linear recurrences with constant coefficients and can be solved easily using the techniques of characteristic equation. The steps to solve the homogeneous linear recurrences with constant coefficients is as follows.

1. Write the recurrence relation in characteristic equation form.
2. Change the characteristic equation into characteristic polynomial of degree $k$.
3. Find the roots of the characteristic polynomial. A polynomial $p(x)$ of degree $k$ has exactly $k$ roots i.e. $r_1, r_2, …, r_k$.
4. The solution of this recurrence relation, if the roots are distinct, is
   $$T(n) = \sum_{i = 1}^k c_ir_i^n$$
   Where $c_1, c_2, …, c_k$ are constants.
5. Find the value of constants $c_1, c_2, …, c_k$ by using the boundary conditions. If there are 3 constants then we need 3 equations.
6. If the roots are not distinct then the solution becomes
   $$T(n) = \sum_{i = 1}^l \sum_{j = 0}^{m_i -1 } c_{ij}n^jr_i^n$$
   Where $r_1, r_2,…, r_l$ are the $l$ distinct roots of the characteristics polynomial and $m_1, m-2, …, m_l$ are their multiplicities respectively.

We use these steps to solve few recurrence relations starting with the Fibonacci number. The Fibonacci recurrence relation is given below.
$$T(n) = \begin{cases} n & \text{ if } n = 1 \text{ or } n = 0\\ T(n - 1) + T(n - 2) & \text{otherwise} \end{cases}$$
First step is to write the above recurrence relation in a characteristic equation form. For this, we ignore the base case and move all the contents in the right of the recursive case to the left i.e.
$$T(n) - T(n - 1) - T(n - 2) = 0 $$
Next we change the characteristic equation into a characteristic polynomial as
$$x^2 - x - 1 = 0$$
The roots of this characteristic polynomial are
$$r_1 = \frac{1 + \sqrt{5}}{2} \text{ and } r_2 = \frac{1 - \sqrt{5}}{2}$$
Since the roots are distinct, the solution is, therefore, of the form
$$T(n) = c_1r_1^n + c_2r_2^n = c_1\left (\frac{1 + \sqrt{5}}{2} \right )^n + c_2 \left (\frac{1 - \sqrt{5}}{2} \right )^n$$
The value of $c_1$ and $c_2$ can be calculated using the base conditions. We know that $T(0) = 0$ and $T(1) = 1$. If we put these two values we get,
$$\begin{align} & c_1 + c_2 = 0 \\
& r_1c_1 + r_2c_2 = 1\end{align}$$
Solving these equations, we get
$$c_1 = \frac{1}{\sqrt{5}} \text{ and } c_2 = -\frac{1}{\sqrt{5}}$$
Thus,
$$T(n) = \frac{1}{\sqrt{5}}\Bigg [ \left (\frac{1 + \sqrt{5}}{2} \right )^n - \left (\frac{1 - \sqrt{5}}{2} \right )^n \Bigg ]$$

Consider another recurrence,
$$T(n) = \begin{cases} n & \text{ if } n = 0, 1 \text{ or } 2\\ 5T(n - 1) - 8T(n - 2) + 4T(n - 3) & \text{otherwise} \end{cases}$$
First we write the characteristic equation
$$T(n) - 5T(n - 1) + 8T(n - 2) - 4T(n - 3) = 0$$
The characteristic polynomial is,
$$x^3 - 5x^2 + 8x - 4 = 0$$
The roots are $r_1 = 1$ of multiplicity $m_1 = 1$ and $r_2 = 2$ of multiplicity $m_2 = 2$. Since roots are repeated, the solution is
$$T(n) = c_11^n + c_22^n + c_3n2^n$$
The base conditions give,
$$\begin{align} & c_1 + c_2 = 0 \\
& c_1 + 2c_2 + 2c_3 = 1 \\
& c_1 + 4c_2 + 8c_3 = 2
\end{align}$$
Solving these equations, we get $c_1 = -2, c_2 = 2 $ and $c_3 = -\frac{1}{2}$. Therefore
$$T(n) = 2^{n + 1} - n2^{n - 1} - 2$$

Inhomogeneous recurrences

In homogeneous recurrences the linear combination of $T(n - i)$ terms is zero. But in inhomogeneous recurrences, the linear combination is not equal to zero and therefore the solution is more difficult than the homogeneous recurrences. Inhomogeneous recurrences take the following form
$$a_0T(n) + a_1T(n - 1) + … + a_kT(n - k) = b^np(n)$$
Where $b$ is a constant and $p(n)$ is a polynomial in $n$ of degree $d$.

To get the characteristic polynomial of an inhomogeneous recurrence, we follow the exact same procedure as the homogeneous for the left part of the equation and for the right part we multiply the characteristic polynomial by $(x - b) ^ {d + 1}$

Example 1: Consider the recurrence,
$$T(n) - 2T(n - 1) = 3^n$$
The right side must be in $b^np(n)$ format. We can easily change the right side to match the format as
$$T(n) - 2T(n - 1) = 3^nn^0$$
Here $b = 3$ and $d = 0$. The characteristic polynomial of the left part of the equation is (exactly same as the homogeneous one)
$$T(n) = (x - 2) = 0$$
Now we multiply this with $(x - b) ^ {d + 1}$ to get
$$(x - 2)(x - 3) = 0$$
This is the characteristic polynomial and we can easily solve this using the techniques discussed in the homogeneous section.

Example 2: Consider another recurrence,
$$T(n) = 2T(n - 1) + n$$
This can be written as
$$T(n) - 2T(n - 1) = 1^nn$$
Comparing the right hand side with $b^np(n)$, we get $b = 1$ and $d = 1$. Therefore the characteristic polynomial is
$$(x - 2)(x - 1)^2 = 0$$
This has repeated roots and we can solve this using the techniques discussed above.

Change of variable

Sometimes changing the variable in a recurrence relation helps to solve the complicated recurrences. By changing the variable, we can convert some complicated recurrences into linear homogeneous or inhomogeneous form which we can easily be solved. At last, we put the original variable back to the recurrence to get the required solution. Let me explain this with the help of an example.

Example: Consider a recurrence
$$T(n) = 3T(n/2) + n$$
In above recurrence relation, the value of $n$ is reduced to half in every iteration. If we replace $n$ with $2^i$, we get
$$T(2^i) = 3T(2^{i - 1}) + 2^i$$
If we let $T(2^i) = t_i$, $T(2^{i - 1})$ becomes $t_{i - 1}$ and the recurrence relation converts to
$$t_i - 3t_{i - 1} = 2^i$$
This is linear inhomogeneous equation with $b = 1$ and $d = 0$. The characteristic polynomial is
$$(x - 3)(x - 2) = 0$$
It has roots $r_1 = 3$ and $r_2 = 2$. The solution will be in the form
$$t_i = c_13^i + c_22^i$$
Initially we changed variable $n$ to $2^i$. $n$ and $2^i$ will be equal when $i = \log_2 n$. Therefore,
$$t_{\log_2 n} = c_13^{\log_2 n} + c_22^{\log_2 n}$$
We let $T(2^i) = t_i$, and thus $T(n) = t_{\log_2 n}$
$$T(n) = c_13^{\log_2 n} + c_22^{\log_2 n}$$
or
$$T(n) = c_1n^{\log_2 3} + c_2n$$
Using the base conditions, value of $c_1$ and $c_2$ can be easily calculated.

References

1. Brassard, G., & Bratley, P. (2008). Fundamentals of Algorithmics. New Delhi: PHI Learning Private Limited.