Last Updated on 4 years by ICT Byte

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 a_n = c₁a_n−1 + c₂a_n−2 + · · · + c_ka_n−k, be the recursive relation with all c_i constants.

If the characteristic equation

r ^k − c₁r ^k−1 − c₂r ^k−2 − · · · c_k = 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