2 min read

Different types of recurrence relations and their solutions

A recurrence relation is an equation that defines a sequence based on a rule that gives the next term as a function of the previous term(s). The simplest form of a recurrence relation is the case where the next term depends only on the immediately previous term.
Different types of recurrence relations and their solutions

In this blog we will see how we can solve different types of recurrence relations using different approaches.

Type 1: Divide and conquer recurrence relations –

T(n) = 2T(n/2) + cn

These types of recurrence relations can be easily solved using Master Method.
For recurrence relation T(n) = 2T(n/2) + cn, the values of a = 2, b = 2 and k =1. Here logb(a) = log2(2) = 1 = k. Therefore, the complexity will be Θ(nlog2(n)).

Type 2: Linear recurrence relations –

Example-  T(n) = T(n-1) + n for n>0 and T(0) = 1

These types of recurrence relations can be easily solved using substitution method.

T(n) = T(n-1) + n

= T(n-2) + (n-1) + n

= T(n-k) + (n-(k-1))….. (n-1) + n

Substituting k = n, we get

T(n) = T(0) + 1 + 2+….. +n = n(n+1)/2 = O(n^2)

Type 3: Value substitution before solving –

Sometimes, recurrence relations can’t be directly solved using techniques like substitution, recurrence tree or master method. Therefore, we need to convert the recurrence relation into appropriate form before solving.

For Example T(n) = T(√n) + 1

To solve this type of recurrence, substitute n = 2^m as:

T(2^m) = T(2^m /2) + 1 Let T(2^m) = S(m), S(m) = S(m/2) + 1

Solving by master method, we get

S(m) = Θ(logm) As n = 2^m or m = log2(n), T(n) = T(2^m) = S(m) = Θ(logm) = Θ(loglogn)

Different types of recurrence relations and their solutions - GeeksforGeeks
A computer science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
https://www.geeksforgeeks.org/different-types-recurrence-relations-solutions/

#Recurrence #Relations #Probyto #ProbytoAI

Subscribe and follow us for latest news in Data Science and Machine learning and stay updated!
Facebook: https://facebook.com/probyto
Twitter: https://twitter.com/probyto
LinkedIn: https://linkedin.com/company/probyto
Instagram: https://instagram.com/probyto