**Algorithm Analysis Of Recurrence/Recursive Relations Using Substitution Method | Part 2 of 4 |**

**Analysis of a recurrence relation using Substitution Method**

**Objective**: in this blog post we will discuss how to analyze the complexity of a recurrence relation using substitution method. Steps and how to make a good guess related to the same.

Substitution method, as the name implies we substitute different values to find the complexity of the recursive function. **Two important steps** related are as follow:

- Guess a particular solution in asymptotic form for the given recurrence relation.
- Verify the guess using mathematical induction and find the value of constant C.

Let us understand substitution method using an example.

Consider the recurrence relation:

We wish to prove that T(n) = O(n^{2}), then its sufficient to show that T(n) <= Cn^{2} . Hence the **first part** of substitution method is to make an assumption. So we make an assumption that T(a) <= Ca^{2} in order to prove T(n) = O(n^{2}). Hence,

T(a) = Ca^{2 }where 1 < a < n-1

The **second step** is to prove our assumption correct using mathematical induction. By substituting the induction hypothesis we get,

We just proved using induction a recurrence relation using substitution method. We made an assumption and then proved our assumption is right using mathematical induction.

**Trick for making a good guess**

If a recurrence relation is of the form i.e.

T(n) = aT(n/b) + F(n)

**Case 1** : If a = b = 2, then

T(n) = O(F(n)log n) is a good guess

**Case 2** :If a = 1 and b = any value, then

T(n) = O(log n) is a good guess

**Case 3**: If a != 1 and b > a, then

T(n) = O[f(n) * n] is a good guess

Now we know how to make a good guess in a substitution method.

That’s all folks. Time for a wrap-up. We have studied how to find complexity of a recurrence relation using substitution method and tried to understand what a good guess is. In the next tutorial we will discuss the next method i.e. **Iterative method** to find the complexity of a recurrence relation.