- It can be solved in terms of itself
- Recurrence relation defines sequenced based on rule those next terms as a function of previous terms.
- Next term is function of pervious terms.
- Defined by itself (in term of previous terms)
- Can model the cpmplexity of divide and conquer algorithm
Solving Recurrence Relations
- To define the term by itself
- To find the complexity
Let an = c1an−1 + c2an−2 + · · · + ckan−k, be the recursive relation with all ci constants.
If the characteristic equation
r k − c1r k−1 − c2r k−2 − · · · ck = 0 has t distinct roots r1, r2, r3,…rt with multiplicity m1, m2, m3…mt, then it has solution
Solving Recurrence Relation to find Complexity
- Iteration method
- Substitution method
- Recursion Tree method
- Master Method