Recurrences in Algorithms | DSA Tutorials

In algorithms, a recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs. When an algorithm contains a recursive call to itself, its running time can often be described by a recurrence equation or recurrence, which describes the overall running time on a problem of size n in terms of the running time on smaller inputs. For example, a recurrence for the merge sort is given below:

Let’s see some methods for solving the recurrences so that the running time for an algorithm can be determined.

Recurrence-solving Methods

1. Substitution Method
2. Iteration Method
3. Recursion Tree Method
4. Master Method

Substitution Method

This method of solving recurrence consists of guessing the form of the solution and using induction to solve. In this method, the guessed answer is used in the recurrence equation, and values of some constants are found. If it becomes easy to get the constants using introduction and mathematical tools, then we can say that the guessed form of the solution is the answer to the recurrence; else, some solution form is to be tried. The guessed solution thus establishes either upper or lower bounds on a recurrence. The method is simple, but you must be very close in guessing the solution, and this comes in handy only when you have a rich experience working with recurrences. Let’s take an example to understand this method.

Example 1: Let us determine an upper bound on the recurrence.

Solution

We guess that the solution is

T(n) = O(n log₂ n)

Then, using the definition of the O notation, we have to prove that T(n) <= (cn log₂n) for some legal choice of the constant c > 0. As the ceiling and floor do not affect the running time of the algorithm, we ignore them. Assume the solution is true for n/2 also, thus we can write

The next step in the substitution method is to show that, using mathematical induction, the solution holds for the boundary conditions. Using the base case for the induction proof, taking n = 1 as our boundary condition, we have

Thus, taking n = 1 creates a problem for which our solution holds for the boundary conditions. But as we have seen, asymptotic notation requires us to prove only that T(n) = cn log₂n for some constant n $\ge$ n0, where n0 is our chosen constant. Now taking the value n0 = 2, we show that T(2) and T(3) are good choices for boundary conditions for our recurrence. It is easy to note from the recurrence that T(2) is 4 and T(3) is 5. Now considering T(n) $\le$ cn log₂ n for some constant c $\ge$ 1, we can write T(2) $\le$ c2 log₂2 and T(3) $\le$ c3 log₂3. You can check it yourself that any choice of c $\ge$ 2 will suffice for the base cases of n = 2 and n = 3 to hold. Ignoring the base condition n = 1 in this example tells us one important point that the base case for recurrence can be different from the base case for the recurrence, as we are looking for an n0 such that n $\ge$ n0 satisfies the equation.

Iteration Method

In the iterative substitution, or “plug-and-chug” technique, we iteratively apply the recurrence equation to itself and see if we can find a pattern. This method is different from the substitution method as we do not have to guess the answer, but we iterate the recurrence on the smaller inputs until some termination condition is met. Thus, it requires us to do more algebraic work compared to the substitution method. Let’s understand this with an example.

Example 2: Find the solution of the following recurrence

Solution: Using the iteration method, we write n = n/2 the first time, then n = n/4 the second time and so on. Using this recurrence is iterated as:

It is clear from the last line that the terminating condition or boundary condition is achieved when ${\large \frac {n}{2^i} = 1 }$ i.e. n = 2ⁱ of i = log₂n. Taking T(1), some constant say b, we have

T(n) = nb + bn log₂n

Thus, the solution to the recurrence is T(n) = O(n log₂) n.

Recursion Tree Method

As the name indicates, the recursion tree method is a tree-based method for solving recurrences. This method clearly shows the iterative view of the recurrence, thus allowing us to visualise each iteration process. Each level of the tree shows the expanded nodes. As during iteration we always have the two parts of the expression: one is recursive and the second is non-recursive, every node of the tree gives the same terms of the recurrence. We associate a cost of expansion at every level of the tree. Summing the cost at each level of the three gives the total cost or solution of the recurrence.

This type of method is particularly useful for recurrences that result from the divide-and-conquer strategy for algorithm design and solving techniques. Let’s understand it using an example.

Example 3: Consider the following recurrence

Solve the above recurrence using the recursion tree method.

Solution: The recursion tree for the above recurrence is shown below in Figure 1 (a), simply T(n), and (b) expanded T(n). At the root, we write the non-recursive cost, and the children of every node are recursive terms for T. Figure 1 (c) shows one more expansion by writing the values for T(n/2). We continue expanding each node in the tree by breaking it into its constituent parts as determined by the recurrence.

On the right side of each level, we have written the cost of that problem. At the root level, we have the cost of original recurrence, i.e. bn. At the next level, the cost is due to 2 subproblems of size n/2. The sum of this is bn/2 + bn/2, i.e. bn. Similarly, at the next level, the cost is 4*bn/4, i.e., bn. The depth, number of T’s and size of the problem are shown in the table below. The number of T’s denotes the number of nodes at each level.

The subproblem size of a node at depth i is n/2ⁱ. Thus, the boundary condition when the recursion is terminated is when n/2ⁱ = 1 or, equivalently, when i = log₂ n. Thus, the tree has log₂n + 1 levels (0,1,2, ….,log₂n). The total cost of the recursion is obtained by the cost at the last level plus the cost of all previous levels. The cost at the last level is $\Theta$(2ⁱ), i.e. $\Theta$(2^logn), which in turn becomes $\Theta$(n) as 2^{log n} = n^log2^2, i.e. n. Thus, the total cost is

T(n) = i times (bn) + $\Theta$(n)
= log n bn + $\Theta$(n)
= O (n log n)

Master Method

The master method is used for a particular form of recurrence relations. This method gives the resultant complexity directly without expanding the function. It is, in fact, an application of the Master’s theorem. The Master’s theorem states that if

Depending upon the values of a,b and d

This theorem depends on the same sum rule that we have explained for notations. Here we have two terms to compare: a T(n/b) and f(n). If a term has a higher order, it becomes the order of the whole relation, as per the sum rule. In the application to the analysis of a recursive algorithm, the constants and functions take on the following significance:

• n is the size of the problem.
• a is the number of subproblems in the recursion.
• n/b is the size of each subproblem. Here, it is assumed that all subproblems are essentially the same size.
• f(n) is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions to the subproblems.

Figure 3 illustrates how the recurrence relation form used in Master’s theorem was developed.

Let us take all three cases in detail:

• Case-1 : d > log_ba: This simply means that f(n) has a higher order than the recursive term. Or we can say the operations besides the recursive call in an algorithm consume more time. Hence, the whole relation has the same order as the order of f(n), that is, O(n^d).
• Case-2 : d = log_ba: When both the terms have the same order, then we view the algorithm as f(n) number of steps followed by some c number of recursive calls. The number of recursive calls an input of size n can invoke is given by logbn. Using the product rule, the complexity turns out to be O(n^d log_bn).
• Case-3 : d < log_ba: This means time consumption largely depends on the recursive calls. Hence, the final complexity depends only on its order. The number of recursive calls per algorithm run is a. Reduction in input with every recursive call is that it gets divided by b. Hence, complexity is O(n^log_ba).

Original Master’s theorem allows us to easily calculate the run time of any recursive algorithm in big-O notation without expanding its recurrence relation. In its generic form, the theorem is slightly different and provides asymptotic bounds for a recurrence function. It can be understood as follows:

For recurrence functions of type $T(n) = aT \left ( \frac{n}{b} \right ) + f(n)$

• Case-1 : If f(n) = O(n^{log_b(a) – ε}), for some constant ε > 0, then T(n) = $\theta$(n^log_b(a))
• Case-2 : If f(n) = $\theta$(n^log_b(a)), then T(n) = $\theta$(n^log_b(a)logn)
• Case-3 : If f(n) = $\Omega$(n^{log_b(a) + ε}), for some constant ε >= 0, then T(n) = $\theta$(f(n))

For the last case to be applicable, one extra condition should be satisfied, f(n/b) <= cf(n), for some constant c < 1. We might need this form only for certain applications, as seen in examples. The method can be better understood by applying it to various recurrence relations:

Example 3: Solve the following recurrence relation using Master’s Method.

Solution: On comparing with $T(n) = aT \left ( \frac{n}{b} \right) + f(n)$ we get

a = 3, b = 3 $\Rightarrow log_ba = log_33 = 1$
f(n) = kn = O(n) $\Rightarrow d = 1$
Since log_ba = d, it is the second case.
T(n) = O(n^dlog_bn) = O(n log₃n).