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
- 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.
- 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.
- 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.
- For each recursive call, notice the size of the input passed as a parameter.
- Calculate the running time of operations that are done after the recursion calls.
- 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 | int fact(int n) { |
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 | int fib(int n) { |
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}$$