Recurrence:
The term Recurrence can be defined as any kind of inequality or equation that focuses on the value over the small inputs of the function. The running time of an algorithm with recursive calls can be easily described by recurrence.
This is the reason that recurrence is often used in Divide-and-Conquer problems.
There are 3 ways of solving recurrence:
- SUBSTITUTION METHOD – A guess for the solution is made, and then we prove that our guess was incorrect or correct using mathematical induction.
- ITERATION METHOD – We need to draw each and every level of recurrence tree and then calculate the time at each level.
- MASTER METHOD – In this method, we have some predefined recurrence equation cases, and our focus is to get a direct solution for it.
SUBSTITUTION METHOD
- Firstly, guess a solution for the given equation.
- Now, using mathematical induction prove that the guess is correct.
An example is given below to show the method in detail.
