Different Types of Recurrence Relations & Their Solutions | Algorithms - Computer Science Engineering (CSE) PDF Download

Type 1: 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).

Type 2: 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²)

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)

Let us discuss some questions based on the approaches discussed.
Q.1. What is the time complexity of Tower of Hanoi problem?
(a) T(n) = O(sqrt(n))
(b) T(n) = O(n²)
(c) T(n) = O(2ⁿ)
(d) None
Solution: For Tower of Hanoi, T(n) = 2T(n - 1) + c for n > 1 and T(1) = 1. Solving this,
T(n) = 2T(n - 1) + c
        = 2(2T(n - 2) + c) + c  = 2² * T(n - 2) + (c + 2c)
       = 2^{k * T}(n - k) + (c + 2c + .. kc)
Substituting k = (n - 1), we get
T(n) = 2^{(n - 1)}*T(1) + (c + 2c + (n - 1)c) = O(2^n)

Q.2. Consider the following recurrence:
T(n) = 2 * T(ceil (sqrt(n) ) ) + 1, T(1) = 1
Which one of the following is true?
(a) T(n) = (loglogn)
(b) T(n) = (logn)
(c) T(n) = (sqrt(n))
(d) T(n) = (n)
Solution: To solve this type of recurrence, substitute n = 2^m as:
T(2^m) = 2T(2^m / 2) + 1
Let T(2^m) = S(m),
S(m) = 2S(m / 2) + 1
Solving by master method, we get
S(m) = Θ(m)
As n = 2^m or m = log2n,
T(n) = T(2^m) = S(m) = Θ(m) = Θ(logn)