Substitution Method
The Substitution Method Consists of two main steps: Guess the Solution. 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 T (n) ≤c logn. Put this in given Recurrence Equation. T (n) ≤c log + 1 ≤c log + 1 = c logn-clog 2 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) ≤2c log +n ≤cnlogn-cnlog2+n =cn logn-n (clog2-1) ≤cn logn for (c≥1) Thus T (n) = O (n logn) . 2. Iteration Methods It means to expand the recurrence and express it as a summation of terms of n ...