What is recurrence relation?

A recurrence relation or recursive relation is an equation that represents a function in terms of the values of its smaller inputs. Every recurrence relation T(n) is a recursive function of integer n and consists of a base case and a recursive case.

For example, in a Fibonacci numbers sequence, the recurrence relation will be F(n) = F (n-1) + F (n-2), where f1 = 1 and f2 = 1 will be the initial (base) conditions for the Fibonacci sequence.

Recursive function and recursion

Before studying recursive relations, it is necessary to understand the meaning of a recursive function and recursion.

• Recursive function: A recursive function is defined as a function that repeatedly calls itself directly or indirectly.
• Recursion: The process where a function repeatedly calls itself is called recursion.

Substitution approach

According to the substitution method, a guess for the solution is first made, and then its correctness is proved using mathematical induction. This approach is effective. However, it is only applicable to situations where guessing the form of response is straightforward. The method can also be used to find the upper and lower boundaries on recurrences.

Consider the following example:

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

Assume the particular solution is T(n) = O(n log n). Now, it is required to prove the correctness of the assumption by applying mathematical induction.

To prove: T(n) <= cn log n.

Hence, it can be assumed that the equation is true for values smaller than n.

Therefore,

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

<= 2cn/ 2 log (n/2) + n

= cn log n - cn log 2 + n

= cn log n - cn + n

<= cn log n

Iteration approach

Iteration is defined as the process to expand the recurrence relation and represent it as a summation of n terms and initial conditions. This method may contain more algebra as compared to the substitution method. Its solution can be assigned boundaries using techniques for evaluating summations.

Consider the following recurrence relation:

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

Now, by solving it using the iteration approach, the particular solution will be:

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

  = [T (n-2) + 1] + 1 (The term T(n-1) is expanded )

  = [T (n-3) + 1] +2

= T (n-4) + 4

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

T(n-k) = T(1) = θ(1)

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

T(n) = 1 + n-1

T(n) = n = θ(n)

Recursion tree approach

The recursion tree method is like the graphical version of the iteration method. In this approach, a recurrence tree is created to measure the time taken by every level of the tree. For the final sum, the work done at all levels is considered.

In other words, initially, the given recurrence is considered as the root node. This root node is divided into equal parts to form a new level. Each node formed in the new level is then taken as the root and further divided to form sub-levels. The process is repeated until a pattern is formed in the levels.

Consider the following example:

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

By solving this equation using the recursion tree method, the solution will be as follows:

Step 1: Begin by drawing a recursion tree for the recurrence relation.

Here the equation represents a problem of size n which is divided into two sub-problems of size n/2. The sub-problem is then divided into two sub-problems of size n/4 and so on. The layer at the bottom will reduce to 1. Hence, the recursion tree will be as below:

The recurrence relation represents a problem of size n, which is divided into its sub-problems and the solution obtained after combining the results is n. Similarly, after dividing the sub-problems, the solution will be n/2 and so on. This is represented using the tree below:

Step 2: The cost at each level of the tree will be n.

Step 3: The total number of levels in the tree will be n/2⁰, n/2¹, n/2², up to n/2^k. For 'k' levels.

Step 4: Now assume that at some level x, the size of the sub-problem becomes 1.

Therefore, n/2^x = 1.

            2^x = n

Step 5: By taking log on both sides,

x log2= log n

x = log₂n

• The total number of levels in the tree = log₂n + 1

Step 6: Now, to find the number of nodes in the last level:

The root level has 2⁰ = 1 node.

The next level has 2¹ = 2 nodes.

And so on.

Therefore, the last level (log₂n) will have 2 ^log₂ⁿ = n nodes.

Step 7: The cost of the last level will be n x T (1) = θ(n)

Step 8: The cost of all the recursion tree levels will be in terms of asymptotic notation:

T(n) = n log₂n + θ(n)

= n log₂n + θ(n)

= θ (n log₂n)

Master Theorem approach

The master theorem works for recurrence relations of the type of:

T (n) = a T(n/b) + f(n)

Where, a >= 1 and b > 1

Further, T(n) is defined on non-negative integers by a recurrence relation. The rest of the constants and functions follow the below significance:

• n is the size of the problem.
• a is the number of subproblems in the recurrence relation.
• n/b is the size of every subproblem (All subproblems are considered the same size).
• f(n) is the total work done outside the recursive calls, including the cost of dividing the problem and merging the solutions of the subproblems.

The master theorem has the following three cases:

1. If f(n) = O(n^c) where c < log_ab, then T(n) = θ(n^log_b^a)
2. If f(n) = θ (n^c) where c = log_ab, then T(n) = θ(n_c logba)
3. If f(n) = Ω (n^c) where c > log_ab, then T(n) = θ(f(n))

Consider the following example:

T(n) = 8T(n/2) + 1000n²

Here,

a = 8, b = 2, f(n) = 1000n²

f(n) = O(n^c), where c = 2

This satisfies case 1 of Master’s theorem. Therefore, the solution will be as follows:

log_ba = log₂8 = 3 > c

Hence, according to the master theorem,

T(n) = θ(n³)

A few points to keep in mind before applying the master theorem for recurrence relation problems are:

• Not every problem of the form T(n) = a T(n/b) + f(n) can be solved by applying the master theorem. For instance, the recurrence relation T(n) = 2 T(n/2) + n/ log n cannot be solved by the master theorem.
• Case 2 can be extended for f(n) = θ (n^c log^kn), if f(n) = θ (n^c log^kn) for some constant k >= 0 and c = log_ba, then T(n) = θ (n^c log^k+1n).

Context and Applications

The recurrence relation is a significant topic in data analysis and algorithms. The topic is equally important for competitive exams and students pursuing undergraduate and postgraduate studies in courses like:

• Bachelor in Science (Information Technology)
• Bachelor in Computer Applications
• Bachelor in Computer Science
• Master in Science (Information Technology)
• Master in Computer Applications
• Master in Computer Science

Practice Problems

1. Which type of problems cannot be solved using recursion?

1. Factorial of a number
2. Fibonacci sequence
3. Length of string
4. Problems without base case

Answer: Option d

Explanation: To solve a problem with the recursion method, the recurrence equations must have a base case. Otherwise, the problem will lead to infinite recursion calls. Hence, problems like the Fibonacci sequence, factorial, and length of a string can be solved using recursion.

2. In which case will the recursive function stop calling itself?

1. Best case
2. Worst case
3. Base case
4. On the right-hand side of the equation

Answer: Option c

Explanation: For a recursive function to stop calling itself, there has to be a base case. Once the problem reaches the base case, the function will stop calling itself.

3. Which algorithm calls itself to do some part of the work?

1. Cdot 3 algorithm
2. Characteristic roots polynomial
3. Recursive algorithm
4. Constant coefficients polynomial

Answer: Option c

Explanation: As per the recursive definition, a recursive algorithm calls itself to perform some functions of a given problem.

4. On what do the solutions of the recursion method depend?

1. Larger instances of different characteristic roots polynomial
2. Larger instances of the non-homogeneous equations
3. Smaller instances of the same problem
4. Smaller instances of different non-recursive sequences

Answer: Option c

Explanation: The solution of recurrence equations depends on the solutions of the smaller instances (subproblems) of the same problem.

5. Master’s theorem method is used for solving-

1. Time complexity of a code
2. Recurrence relations
3. Previous terms loops
4. Cdot 3 divide-and-conquer problems

Answer: Option b

Explanation: The master’s theorem approach is used to solve recurrence relations. It can be used to solve any recurrence relation that falls under any one of its three cases (mentioned in this article).

Common Mistakes

Students often apply the master theorem for solving all recurrence relation equations of the type of T(n) = a T(n/b) + f(n). However, it may not work every time.

Related Concepts

• Sorting algorithms
• Asymptotic analysis
• Low bound theory
• Tail recursion
• Complexity analysis of binary search