Solving Recurrence Relation

Here are the 10 questions of recurrence relation.

1. T(n) = T(n – 1) + 1

2. T(n) = T(n – 1) + n

3. T(n) = T(n – 1) + n^2

4. T(n) = T(n – 1) + log n

5. T(n) = 2T(n – 1) + 1/n

6. T(n) = T(n/2) + n

7. T(n) = 2T(n/2) + 1

8. T(n) = 2T(n/2) + n

9. T(n) = T(n/2) + log n

10. T(n) = 2T(n/2) + n/ log n

These recurrence questions are solved by

1. Substitution Method– 

The substitution method comprises 3 steps

(1). Guess the form of the solution

(2). Verify by Induction

(3). Solve for constants.

We substitute the guessed solution for the function when applying the inductive hypothesis to smaller values. Hence the name “Substitution Method” 

2. Iterative Method– 

This method first converts the recursion to a sum. To do this, repeat until the initial conditions are met. T(1) was the required time in the initial state. To transform the recursion, first, decompose T(n) into T(n/2) and then T(n/4). 

3. Recurrence Tree Method– 

The recursive tree method is a graphical representation of a tree-style iterative method that extends a node at each level. Generally, the second term of recurrence C in T(n) = aT(n/b) + C is considered the root. This is useful when using the divide-and-conquer algorithm. Each route and child represent the cost of a single sub-problem.

4. Master’s Theorem–

It is a simplistic way to find time complexity. Question numbers 6 to 8 are solved by the master’s theorem. Master’s method works only for recurrence T(n) = aT(n/b) + c₁*n^k, where a, b, c₁ and k are constant.

5. Extended Master’s Theorem– 

Question no 9 and 10 will be solved by this theorem. But this is a very complex method. Most of the students try to solve questions number 9 and 10 with the master’s theorem. This method will be used only for the recurrence T(n) = aT(n/b) + c₁*n^k*log^pn

where a, b, c₁, k and p are constant.