Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we have presented the Substitution method for finding the Time complexity of an algorithm in detail.

Table of Contents:

- Introduction to Recurrence relations
- Substitution Method
- MCQs on Recurrence relations

# Introduction to Recurrence relations

Recurrence relation is way of determining the running time of a recursive algorithm or program. It's a equation or a inequality that describes a functions in terms of its values and smaller inputs. Now before jumping on to various methods of solving recurrence relation, let's first take a look at the example of recurrence relation.

Let us consider **T(n)** to be the running time of a given problems on size **n**, the problem in our case will be finding the *nth fibonacci number*. Let *F(n)* denote the *nth fibonacci number*, therefore *F(n) = F(n-1) + F(n-2)* and *T(0) = a , a is a constant*.

The recurrence relation will be :

**T(n) = c + T(n-1)**, where c is a constant

There are mainly four methods of solving recurrence relation:

- Substitution method
- Iteration method
- Master method
- Recursion tree method

# Substitution method

In this article at OpenGenus, our primary focus is *Solving recurrence relation via Substitution method*, hence we will deep dive into the process through examples and explanations.

The whole working of the substitution method can be divided into two processes :

- Take a guess at the solution
- Find boundary conditions using the principles of mathematical induction and prove that the guess is correct

Note: Mathematical induction is a proof technique that is vastly used to prove formulas.

Now let us take an example:

**Recurrence relation:** T(1) = 1 and T(n) = 2T(n/2) + n for n > 1

* Step 1:* We guess that the solution is

*T(n) = O(n logn)*

* Step 2:* Let's say

*c is a constant*hence we need to prove that :

*T(n) β€ cn logn*for all

*n β₯ 1*

* Step 3:* Using the above statement we can assume that :

*T(n) β€ cn log(n/2) + n*

*T(n) = cn log(n) - cn log(2) + n*

*T(n) = cn log(n) - cn + n*

*T(n) = cn log(n) + n(1 - c)*

hence

*T(n) β€ cn log(n)*for all c β₯ 1

* Step 4:* Now we need to put the values into the recurrence formula,

*T(2) = 2T(1) + 2 = 4*and

*T(3) = 2T(1) + 3 = 5*, now our task to choose a

*c*that perfectly fits our inequality obtained above in

*step 3*, let say

*c = 2*:

4 β€ 4log(2) and 5 β€ 6log(3) perfectly satisfy the condition, hence we can conclude that

*T(n) β€ 2n log n*for all

*n β₯ 2*, therefore

*T(n) = O(n log n)*

# MCQs on Recurrence relations

**(i) Find the solution of given recurrence relation F(n) = 20F(n-1) - 25F(n-2), where F(0) = 4 and F(1) = 14**

*Ans : b*

**Explanation :** First find the characteristic polynomial i.e. x^2-20x+36=0 in this case, having found the roots find the form of recurrence equation i.e. an=a(2^n)+b(18^n), find the value of a and b using equations F(0) = 4 and F(1) = 14 i.e. a=7/2 and b=-1/2, hence the answer is option b.

**(ii) Determine the recurrence relation for the following series 1,7,31,127,499**

*Ans : c*

**Explanation :** On observing carefully, we see that the difference between the consecutive terms is a factor of 4, therefore 1.4=4,7.4=28,31.4=124 so on, ending term is 3 less than the next term therefore the answer will be option c.

**(iii) Find the solution of given recurrence relation F(n) = 6T(n-1) - 8T(n-2), given that T(0) = 3 and T(1) = 5**

*Ans : b*

**Explanation :** Follow similar steps as mentioned in the first problem.

**(iv) Find the solution of the recurrence relation T(n) = 5T(n-1) + 6T(n-2)**

*Ans : b*

**Explanation :** Just check on the left side of the given equation for all the options individually, we find that 6n satisfies the equation hence answer is option b.

**(v) Find the value of T(2) for the recurrence relation T(n) = 17T(n-1) + 30n, given that T(0) = 3**

*Ans : d*

**Explanation :** First calculate the value for T(1) i.e. T(1) = 17T(0) + 30 = 81, now calculate value of T(2) by putting the value of T(1) in it i.e. T(2) = 17T(1) + 60 = 1437, that is our required answer.

**Thank You!**