Types of Recurrence Relations

Various types of Recurrence Relations are:

1. Linear Recurrence Relations
2. Divide and Conquer Recurrences
3. Substitution Recurrences
4. Homogeneous Recurrences
5. Non-Homogeneous Recurrences

1. Linear Recurrence Relations:

Following are some of the examples of recurrence relations based on linear recurrence relation.

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.
For example,

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)

2. Divide and conquer recurrence relations:

Following are some of the examples of recurrence relations based on divide and conquer.

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

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)).
Similarly for recurrence relation T(n) = 2T(n/2) + √n, the values of a = 2, b = 2 and k =1/2. Here logb(a) = log2(2) = 1 > k. Therefore, the complexity will be Θ(n).

3. Substitution Recurrences:

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)

4. Homogeneous Recurrence Relations:

A homogeneous recurrence relation is one in which the right-hand side is equal to zero. Mathematically, a homogeneous recurrence relation of order k is represented as:

with the condition that the above equation equates to 0.

Example:

5. Non-Homogeneous Recurrence Relations:

A non-homogeneous recurrence relation is one in which the right-hand side is not equal to zero. It can be expressed as:

where g(n) is a function that introduces a term not dependent on the previous terms. The presence of g(n) makes the recurrence non-homogeneous.
Example:

In this case, the term 3^n on the right-hand side makes the recurrence non-homogeneous.

Have you ever wondered how to calculate the time complexity of algorithms like Fibonacci Series, Merge Sort, etc. where the problem is solved by dividing it into subproblems. This is done by analyzing the Recurrence Relations of these algorithms. In this article, we will learn about the basics of Recurrence Relations and how to analyze them.