Recurrence Relations | Solving Recurrence Relation to find Complexity


Recursive Algorithm

  • 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

  1. Iteration method
  2. Substitution method
  3. Recursion Tree method
  4. Master Method
Facebook Comments