Masters of Computer Science Design and Analysis of Algorithm

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

Theorem

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
About Author

ICT Byte