Recurrence relation { Substitution Method }

                    Recurrence relation

Introduction
Recurrence:
Definition :  A recurrence is an equation or simply an inequality that describes a function in the terms of its values on smaller inputs. 
☛The running time of the recursive algorithm can be obtained by a recurrence. To solve a recurrence relation means to obtain a function defined on the natural numbers that satisfies the recurrence.
Example :   Fibonacci series is f(n)=f(n−1)+f(n−2).....

For solving the recurrence we will discuss following methods :

1. Substitution Method.
2. Master Theorem.
3. Recursion Tree Method.

1.  Substitution Method :   The substitution method is a condensed way of proving an asymptotic bound on a recurrence by induction. It is able to prove upper bounds for almost all recurrences. It is used in calculating the time complexity of recurrence relations.

 ✍The substitution method for solving recurrences we have :
☛ Guess the form of the solution.
  ☛  Use mathematical induction to find the constants and show that the solution works.

Example 1: Find the time complexity of T(n)=2T(n/2)+C,                               T(1)=1.
Example 2: T(n) =3T(n/4)+n  Time complexity =? 
                      By substitution method.


                                Solutions