Web
Analytics Made Easy - StatCounter

Recurrence Relation

In an Analysis of Algorithm, recurrence relations are used to analyze the running time of a recursive function. The running time of a recursive function is denoted by $T(n)$ where $n$ is the size of the input. In recurrence relation, the running time of a recursive function of input size $n$ is expressed in terms of the running time of the lower value of $n$. For example
$$T(n) = T(n - 1) + O(1)$$
Here, the running time for size $n$ is equal to the running time for size $n - 1$ plus a constant time. Usually, the running time $T(n)$ is expressed as a conditional statement having the following two conditions

  1. Base Case: The base case is the running time of an algorithm when the value of $n$ is small such that the problem can be solved trivially.
  2. Recursive case: The recursive running time is given by a recurrence relation for a large value of $n$.

Using base and recursive case, the running time of a recursive function would look like the following.
$$T(n) = \begin{cases} O(1) & \text{ if } n \le 2 \\
T(n - 1) + O(1) & \text{otherwise}
\end{cases}$$
This recurrence relation can be interpreted as follows - when the value of $n$ is less than or equal to 2, we can find the solution trivially in $O(1)$ time. If the value of $n$ is greater than 2, we can use the recurrence relation to find the running time.

So far we have learned what is recurrence relation and how to represent it in a conditional statement. Next, we will how to write recurrence relation looking at the code. The process of translating a code into a recurrence relation is given below.

  1. The first thing to look in the code is the base condition and note down the running time of the base condition. Remember: every recursive function must have a base condition.
  2. For each recursive call, notice the size of the input passed as a parameter.
  3. Calculate the running time of operations that are done after the recursion calls.
  4. Finally, write the recurrence relation.

Let us try to translate some code example starting with the factorial function. A C programming code to calculate the factorial of a number $n$ is shown below.

1
2
3
4
5
6
7
int fact(int n) {
if (n == 0) {
return 1;
}

return n * fact(n - 1);
}

The base condition happens when the value of $n$ is 0. We can find the value of $0!$ in constant time $O(1)$ trivially i.e. for base condition
$$T(0) = O(1)$$
Next, we look for the recursive call. There is only one recursive call with input size $n - 1$ and after the recursive function returns we do a simple multiplication that takes $O(1)$ time i.e. the total running time is
$$T(n) = T(n - 1) + O(1)$$
Combining this with the base condition, we get
$$T(n) = \begin{cases} O(1) & \text{ if } n = 0 \\
T(n - 1) + O(1) & \text{otherwise}
\end{cases}$$

Let us do another example of calculating nth Fibonacci number. The C code for this is shown below.

1
2
3
4
5
6
7
8
int fib(int n) {
if (n <= 1)
{
return n;
}

return fib(n - 1) + fib(n - 2);
}

When the value of $n$ is 0 or 1, we can trivially find the corresponding Fibonacci number in constant time i.e.
$$T(n) = O(1) \text{ if } n \le 1$$
There are two recurrence relations - one takes input $n - 1$ and other takes $n - 2$. Once we get the result of these two recursive calls, we add them together in constant time i.e.
$$T(n) = T(n - 1) + T(n - 2) + O(1)$$
Combining with the base case, we get
$$T(n) = \begin{cases} O(1) & \text{ if } n \le 1 \\
T(n - 1) + T(n - 2) + O(1) & \text{otherwise}
\end{cases}$$