Substitution Method:

The Substitution Method Consists of two main steps:

1. Guess the Solution.
2. Use the mathematical induction to find the boundary condition and shows that the guess is correct.

For Example1 Solve the equation by Substitution Method.

	T (n) = T + n

We have to show that it is asymptotically bound by O (log n).

Solution:

For T (n) = O (log n)

We have to show that for some constant c

1. T (n) ≤c logn.  

Put this in given Recurrence Equation.

	T (n) ≤c log+ 1

≤c log

+ 1 = c logn-clog2 2+1
			≤c logn for c≥1

Thus

T (n) =O logn.

Example2 Consider the Recurrence

T (n) = 2T+ n n>1

Find an Asymptotic bound on T.

Solution:

We guess the solution is O (n (logn)).Thus for constant 'c'.
 T (n) ≤c n logn
Put this in given Recurrence Equation.
Now,
  T (n) ≤2clog +n
      ≤cnlogn-cnlog2+n
      =cn logn-n (clog2-1)
      ≤cn logn for (c≥1)

Thus

T (n) = O (n logn)
.