Connect with us

Design and Analysis of Algorithm

Recurrence Relations | Solving Recurrence Relation to find Complexity

Published

on

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
Facebook Comments
Advertisement
Advertisement

People are Loving

Facebook

Advertisement

Events

  1. “Data Science and ML Workshop” – CSITAN Purwanchal

    August 7 @ August 7 - August 7

10 Hits in 30 Days

DMCA
PROTECTED