Substitution Method

Substitution Method is very famous method for solving any recurrences. There are two types of substitution methods-

1. Forward Substitution
2. Backward Substitution

1. Forward Substitution:

It is called Forward Substitution because here we substitute recurrence of any term into next terms. It uses following steps to find Time using recurrences-

• Pick Recurrence Relation and the given initial Condition
• Put the value from previous recurrence into the next recurrence
• Observe and Guess the pattern and the time
• Prove that the guessed result is correct using mathematical Induction.

Now we will use these steps to solve a problem. The problem is-

T(n) = T(n-1) + n, n>1

T(n) = 1, n=1

Now we will go step by step-

1. Pick Recurrence and the given initial Condition:

T(n)=T(n-1)+n, n>1T(n)=1, n=1

2. Put the value from previous recurrence into the next recurrence:

T(1) = 1T(2) = T(1) + 2 = 1 + 2 = 3T(3) = T(2) + 3 = 1 + 2 + 3 = 6T(4)= T(3) + 4 = 1 + 2 + 3 + 4 = 10

3. Observe and Guess the pattern and the time:

So guessed pattern will be-T(n) = 1 + 2 + 3 …. + n = (n * (n+1))/2Time Complexity will be O(n²)

4. Prove that the guessed result is correct using mathematical Induction:

• Prove T(1) is true:
  T(1) = 1 * (1+1)/2 = 2/2 = 1 and from definition of recurrence we know T(1) = 1. Hence proved T(1) is true
• Assume T(N-1) to be true:
  Assume T(N-1) = ((N – 1) * (N-1+1))/2 = (N * (N-1))/2 to be true
• Then prove T(N) will be true:T(N) = T(N-1) + N from recurrence definition
  Now, T(N-1) = N * (N-1)/2So, T(N) = T(N-1) + N = (N * (N-1))/2 + N = (N * (N-1) + 2N)/2 =N * (N+1)/2And from our guess also T(N)=N(N+1)/2Hence T(N) is true.Therefore our guess was correct and time will be O(N²)

2. Backward Substitution:

It is called Backward Substitution because here we substitute recurrence of any term into previous terms. It uses following steps to find Time using recurrences-

• Take the main recurrence and try to write recurrences of previous terms
• Take just previous recurrence and substitute into main recurrence
• Again take one more previous recurrence and substitute into main recurrence
• Do this process until you reach to the initial condition
• After this substitute the the value from initial condition and get the solution

Now we will use these steps to solve a problem. The problem is-

T(n) = T(n-1) + n, n>1T(n) = 1, n = 1

Now we will go step by step-

1. Take the main recurrence and try to write recurrences of previous terms:

T(n) = T(n-1) + nT(n-1) = T(n-2) + n – 1T(n-2) = T(n-3) + n – 2

2. Take just previous recurrence and substitute into main recurrence

put T(n-1) into T(n)So, T(n)=T(n-2)+ n-1 + n

3. Again take one more previous recurrence and substitute into main recurrence

put T(n-2) into T(n)So, T(n)=T(n-3)+ n-2 + n-1 + n

4. Do this process until you reach to the initial condition

So similarly we can find T(n-3), T(n-4)……and so on and can insert into T(n). Eventually we will get following: T(n)=T(1) + 2 + 3 + 4 +………+ n-1 + n

5. After this substitute the the value from initial condition and get the solution

Put T(1)=1, T(n) = 1 +2 +3 + 4 +…………..+ n-1 + n = n(n+1)/2. So Time will be O(N²)

Recursion is a method to solve a problem where the solution depends on solutions to smaller subproblems of the same problem. Recursive functions (function calling itself) are used to solve problems based on Recursion. The main challenge with recursion is to find the time complexity of the Recursive function. In this article, we will learn about how to find the time complexity of Recursive functions using Substitution Method.