Substitution Method Examples

For Complete YouTube Video: Click Here

In this class, we will try to understand the Substitution Method Examples.

We have already discussed the concepts of Substitution Method in our previous class.

Here we will consider the following example.

In the above equation, to find T(n)= (n) + T(n – 1) – (1), we have to find T(n-1).

To get the value of T(n-1), we have to substitute n-1 in the place of n.

T(n-1) = (n – 1) + T(n-2) – (2).

Similarly, T(n-2) = (n – 2) + T(n-3) – (3).

By substituting the value of T(n-1) in the equation (1), we get T(n) = n + (n – 1) + T(n-2).

Now substitute the value of T(n-2) in the above equation.

By substituting, we will get T(n) = n + (n – 1) + (n – 2) + T(n-3).

If we substitute the values, we will get the equation below.

T(n) = n + (n – 1) + (n – 2) + (n-3) + . . . . + (n – k) + T(n – (k + 1))

This way, we can substitute to any length, but the algorithm will stop executing when the value of n – (k + 1) = 1.

Now, n – k – 1 = 1.

n – k = 2.

Substitute the value n – k in the above equation.

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

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

The above equation looks like the sum of first n natural numbers.

n(n – 1) /2

The order of growth of the algorithm is n².

Therefore the efficiency of the above recurrence equation T(n) = n².