Recurrence Relation

Recurrence relation is an equation that expresses the nth term of a sequence as a function of k preceding terms, for some fixed k (independent from n), which is called the order of the relation. Once k initial terms of a sequence are given, the recurrence relation allows computing recursively all the remaining terms of the sequence.

Analyzing control statements are easy because they are iterative. Many algorithms are recursive in nature and when we analyze them we get a recurrence relation for time complexity.

We get running time as a function of n(input size) and we get the running time on inputs of smaller size.
A recurrence relation recursively defines a sequence where the next term is a function of previous term.

Methods to solve recurrence relation

1. Substitution ***

2. Homogeneous (characteristic equation)

3. Inhomogeneous

4. Master Theorem ***

5. Recurrence tree ***

6. Intelligent guess work

7. Change of variable

8. Range transformations

Substitution Method

In substitution method we make guess for the solution then we use mathematical induction to prove the guess is correct or incorrect. This is the most acceptable method as it always works for any recurrence relation, although it takes too much time in calculation.

Example - 1

$$T(n)T(n)$$ is the time to solve instance of size n, and $$T(n-1)T(n-1)$$ is the time to solve instance of size $$n-1n-1$$.

Replacing $$nn$$ by $$n-1n-1$$ and $$n-2n-2$$, we can write the following equations.

Substituting equation 3 in 2, we'll get equation 4 as follows:

By substituting equation 4 in 1, we'll get the following equation:

From above observation we can write the general form of the equation 1 as follows.

Suppose, if we take $$k=nk=n$$ then,

Example - 2

If we rewrite the equation then we'll get that,

By relpacing $$nn$$ by $$n-1n-1$$, we'll get the following

By replacing $$nn$$ by $$n-2n-2$$, we'll get the following

If we substitute eq (3) into eq (2), then we'll get the following

Substituting the value of eq (4) into eq (1), we'll get the following

From the above observation, we can write the general form of the equation as below

Suppose if we take $$k=nk=n$$, then we could rewrite the above equation as follows.

Master Theorem

The master theorem always yields asymptotically tight bounds to recurrences from divide and conquer algorithms that partition an input into smaller subproblems of equal sizes, solve the subproblems recursively, and then combine the subproblem solutions to give a solution to the original problem. The time for such an algorithm can be expressed by adding the work that they perform at the top level of their recursion (to divide the problems into subproblems and then combine the subproblem solutions) together with the time made in the recursive calls of the algorithm.

Suppose if we have the recurrence of the following form:

The above recurrence relation constitutes of three parts. $$T(n)T(n)$$ is the time taken to solve a problem of size $$nn$$, $$aa$$ is the number of sub-problems, $$T(n\mathrm{/}b)T(n/b)$$ is the time required to solve a sub-problem and $$f(n)f(n)$$ is the time required divide and conquer the sub-problems.

There are three cases:

1. Case 1 : if $$f(n)f(n)$$ is in $$O(n^{{\log }_{b}a})O(n^\{\; \backslash log\_ba\})$$, i.e $$f(n)\le n^{{\log }_{b}a}f(n)\; \backslash le\; n^\{\; \backslash log\_ba\}$$ then $$T(n)=n^{{\log }_{b}a}T(n)\; =\; n^\{\; \backslash log\_ba\}$$

2. Case 2 : if $$f(n)f(n)$$ is in $$\mathrm{\Theta }(n^{{\log }_{b}a})\backslash Theta(n^\{\; \backslash log\_ba\})$$, i.e $$f(n)=n^{{\log }_{b}a}f(n)\; =\; n^\{\; \backslash log\_ba\}$$ then $$T(n)=n^{{\log }_{b}a}\lg nT(n)\; =\; n^\{\; \backslash log\_ba\}\; \backslash lg\; n$$

3. Case 3 : if $$f(n)f(n)$$ is in $$\mathrm{\Omega }(n^{{\log }_{b}a})\backslash Omega(n^\{\; \backslash log\_ba\})$$, i.e $$f(n)\ge n^{{\log }_{b}a}f(n)\; \backslash ge\; n^\{\; \backslash log\_ba\}$$ then $$T(n)=f(n)T(n)\; =\; f(n)$$

Example - 1

Here, $$a=2,b=2a=2,\; b=2$$. So, $$n^{{\log }_{b}a}=nn^\{\backslash log\_ba\}=n$$
Also, $$f(n)=\mathrm{\Theta }(n)=cnf(n)=\backslash Theta(n)=cn$$.
Case 2 applies : $$T(n)=\mathrm{\Theta }(n\lg n)T(n)\; =\; \backslash Theta(n\; \backslash lg\; n)$$

Example - 2

Here, $$a=1,b=2a=1,\; b=2$$. So, $$n^{{\log }_{b}a}=n^{{\log }_{2}1}=n^0=1n^\{\backslash log\_ba\}=n^\{\backslash log\_21\}=n^0=1$$
Also, $$f(n)=\mathrm{\Theta }(1)=1f(n)=\backslash Theta(1)=1$$.
Case 2 applies : $$T(n)=\mathrm{\Theta }(\log n)T(n)\; =\; \backslash Theta(\backslash log\; n)$$

Example - 3

Here, $$a=4,b=2a=4,\; b=2$$. So, $${\log }_{b}a=2\backslash log\_ba=2$$ and $$n^{{\log }_{b}a}=n^{2}n^\{\backslash log\_ba\}=n^2$$

$$f(n)=nf(n)\; =\; n$$
So, $$f(n)\le n^2⟹f(n)isO(n^{{\log }_{b}a})f(n)\; \backslash le\; n^2\; \backslash implies\; f(n)\; \backslash \; is\; \backslash \; O(n^\{\backslash log\_ba\})$$
Case 1 applies : $$T(n)=\mathrm{\Theta }(n^2)T(n)\; =\; \backslash Theta(n^2)$$

Recurrence Tree Method

In recurrence tree method, each node represents the cost of a single sub-problem in the set of recursive function invocations. We sum the cost within each level of the tree to obtain a set of per level cost.

We sum the per level cost in-order to determine the total cost of the all levels of the recursion.

Here while solving the problem, we divide the problem into sub-problems of equal size.

E.g,

where $$a>1,b>1a>1,\; b>1$$ and $$f(n)f(n)$$ is a given function.

$$f(n)f(n)$$ is the cost of splitting and combining the sub-problems.

In the above diagram, a problem of size n has been divided into two sub-problems of size $$n\mathrm{/}bn/b$$.

Example

The recurrence tree for this recurrence is:

When we add the values across the levels of the recursion tree, we get a value of n for every level. The bottom level has $$2^{\log n}2^\{\backslash log\; n\}$$ nodes and each contributing of $$T(1)T(1)$$.

We have $$n+n+n+\mathrm{.}\mathrm{.}\mathrm{.}ntimesn+n+n+...n\; \backslash \; times$$
So,

Conclusion

We have seen what are the recurrence relations and popular methods to solve them. We have also seen some examples for each method.