Time Complexity of Recursive Function in C

Back to: C Tutorials For Beginners and Professionals

Time Complexity of Recursive Function in C Language

In this article, I will discuss How to Find the Time Complexity of a Recursive Function in C Language. Please read our previous article discussing How Recursion Uses Stack memory in C Language.

How to Find the Time Complexity of a Recursive Function in C Language?

Let us first understand the basic concept for finding the time complexity. We assume that every statement in our program takes one unit of time for execution.

Let me give the idea behind that one. Suppose some books are kept in one place, and you have to move the book and keep it on a shelf or rack. How much time does it take? Maybe half a second, a quarter of a second, maybe if somebody works very slowly, may take one second to keep one book there. The time varies from person to person. So, we don’t mention seconds or milliseconds. We say one unit of time. Suppose you take the example of currency, one dollar, one rupee, and one pound. We say one, but what is the market value that might be different? So, we say one buck or one unit of currency.

In the same way, we assume that every statement takes one unit of time. If that statement is repeated multiple times, then we need to count the frequency and how many times it is executed. That is sufficient for analyzing our function.

Example to Find the Time Complexity of a Recursive Function in C Language:

We are going to use the following function. We will calculate the time complexity of the following recursive function in the C Programming Language.

Let us see what the above function (fun1) is doing. It is doing nothing, just printing. It just prints the value of n.

How much time does it take to print?

It takes one unit of time to print.

How many times the printf is written there?

Only one-time printf is written there. But this is a recursive function. So, it is calling itself again and again. As it is a recursive function, let us find out how many times the printf function is executed. As we already discussed in our How Recursive Works article, we can find this using the tracing or recursion trees.

As you can see in the above tracing tree, it first prints the value 3, then 2, and then the value 1. That means the printf statement is executed three times. So, this recursive function will take 3 units of time to execute when the n value is 3. If we make the n value 5, executing this recursive function will take 5 units of time.

So, we can say for n, it will take n units of time. Coming back to the example, if we have to keep one book on a shelf. You will take one unit of time. For ten books, you will take ten units of time. So, for n number of books, you will n unit of time. The most important point you must remember is that time depends on the number of books.

The time can be represented as the order of n i.e. O(n). The time taken is in order of n.

Time Complexity using Recurrence Relation in C Language:

There is one more method to find the time complexity, i.e., using the recurrence relation. Let us see how to write a recurrence relation and how to solve it to find the time complexity of the recursive function. Using the recurrence relation, let us find the time complexity of the following recursive function.

We assume that the time taken by the above function is T(n), where T is for time. If the time taken for fun1() is T(n), then the total time should be the sum of all the times taken by the statements inside that function.

So, let us look at the statement. Every statement takes one unit of time for execution. See, there is a conditional statement (if (n > 0)) inside the function. How much time it takes for execution, just one unit of time it takes for execution. Then there is a printf statement, which takes one unit of time.

Then there is one more function call statement (fun1(n-1)), and how much time will it take. It also takes one unit of time. No, that is not correct. It will not take one unit of time. This is a function call. It should be the total time taken by that function. It is not just a normal statement. It will call itself again. So, there is something more behind that one. So, we need to know how long that function call takes.

Let us see closely. What we said fun1(int n) function call, the total time is T(n). Then this fun1(n-1) is similar to fun1(int n) one, and here it is n-1. So, the total time taken by this function will be T(n-1) time. Then what is T(n)? As we said, the sum of all the times the statement takes. So, let us take the sum of T(n) =T(n-1)+2. For a better understanding, please have a look at the below image.

So, the recurrence relation is T(n)=T(n-1 )+ 2 when n>0. What happens when n=0 is that it will just check the condition, and it will not enter inside it and will come out. Just checking the condition, so it will take one unit of time. For a better understanding, please have a look at the below image.

So, this is the recurrence formed from that fun1 function. So, the time complexity of the recursive function can be represented in the form of a recurrence relation.

Induction Method or Successive Substitution Method in C Language:

We can also solve this using the induction and successive substitution methods and get the answer. So, let us solve this one. Before solving this, we should know one thing: if we have any constant value there then we should write it as one 1. In our example, the constant value 2 is there, so replace it with 1, as shown below.

So, the recurrence is T(n)=T(n-1) + 1 ———-[eq.1]

We can solve this if we know what is T(n-1)
Since, T(n)=T(n-1) +1
           T(n-1) = T(n-2) +1

So, we can substitute T(n-2) +1 instead of T(n-1). So, the next equation is
T(n)=T(n-2) + 1 + 1
T(n) =T(n-2) + 2 ———[eq.2]

Let us substitute T(n-3) +1 in that place. Then this will be,
T(n)=T(n-3) +1+2
T(n) =T(n-3) +3 ———-[eq.3]

So, we have substituted two times the time we should do this. Let us continue it for K times.
T(n)=T(n-k) +k ———[eq.4]

So, continue substituting until it reduces to a smaller value, n=0. When we don’t know the answer for a bigger expression, then break the bigger one into a smaller one and solve it. We have done the same thing, and we don’t know how much this is, but we know when n=0, then the answer is directly 1. We have tried to reduce this by substituting, and we got that one.

Now, we see that this n-k actually has become 0. Then assume that n-k=0. It means n=k. If we substitute that in [eq.4] it gives,
T(n)=T(n-n) +n
=T(0) +n
=1+n

That solves the problem. We get the answer T(n)=1+n. This can be written as O(n). Earlier, directly from their tracing tree we also have seen n+1 was the number of calls and the time taken by this fun1 function depends on the number of calls.

How do you find the time complexity of recursive functions in C?

Finding the time complexity of recursive functions in C (or any programming language) can be challenging due to the nature of recursion. However, it’s a crucial skill for optimizing and understanding the efficiency of algorithms. The time complexity essentially measures how the runtime of an algorithm grows with the input size. Here’s a guide to analyzing the time complexity of recursive functions:

1. Identify the Base Case
The base case (or cases) determines when the recursion stops. The complexity of reaching the base case is a key factor in determining the overall time complexity.

2. Calculate the Number of Recursive Calls
Understand how many times the recursive function calls itself. This depends on the algorithm and how it breaks down the problem.

3. Determine the Work Done in Each Call
Assess the complexity of the operations performed in each recursive function call, excluding the recursive calls themselves.

4. Use Recurrence Relations
A recurrence relation expresses the total time of a recursive function in terms of the time taken by its recursive calls. For example, if a function T(n) calls itself twice with the argument n/2 and does O(n) work, the recurrence would be T(n)=2T(n/2)+O(n).

5. Solve the Recurrence
This is often the trickiest part. Common methods to solve recurrences include:

• Substitution Method: Guess a bound and then use mathematical induction to prove it.
• Recursion Tree Method: Visualize the recursive calls as a tree and sum the work done at each level.
• Master Theorem: A widely-used shortcut for common types of recurrences. It provides a direct way to get the time complexity if the recurrence fits its format.

Common Patterns in Recursive Time Complexity:

• Linear Recursion: Example: T(n) = T(n-1) + O(1) (like computing the nth Fibonacci number naively). This typically leads to a linear time complexity, O(n), because a single recursive call reduces the problem size by a constant amount.
• Divide and Conquer: Example: T(n) = 2T(n/2) + O(1) (like Merge Sort). This often leads to O(n log n) complexity, as the problem is divided into two halves with each recursive call.
• Multiple Recursive Calls with Constant Subtraction: Example: T(n) = T(n-1) + T(n-2) + O(1) (like the naive Fibonacci sequence calculation). This usually results in exponential time complexity, like O(2^n), because each function call spawns multiple calls.
• Logarithmic Reduction: Example: T(n) = T(n/2) + O(1) (like Binary Search). This leads to logarithmic time complexity, O(log n), because each call reduces the problem size by half.

Example: Calculating Factorial

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

Time Complexity: O(n).
Reason: One recursive call per function reduces n by 1 each time until it reaches 0.

Example: Naive Fibonacci

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

Time Complexity: O(2^n).
Reason: Each call generates two more calls. The number of calls grows exponentially with n.

Example: Binary Search

int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x) return mid;
        if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}

Time Complexity: O(log n).
Reason: The problem size is reduced by half in each step.

Example: Linear Recursion

Consider a simple recursive function that sums the numbers up to n:

int sum(int n) {
    if (n <= 0) return 0;
    return n + sum(n-1);
}

This function has a linear time complexity, O(n), because each call generates only one subsequent call, creating a chain of n calls.

In the next article, I am going to discuss Types of Recursive Functions in C Language with Examples. Here, in this article, I try to explain How to find the time complexity of recursive functions in C Language and I hope you enjoy this Time Complexity of a Recursive Function in C Programming Language article. Please give your feedback and suggestions about this article.