Return home

Time Complexity of Recursive Factorial Algorithm

When you solve a problem, if you develop a systematic method, you can solve a similar problem easily by applying the same steps in the method. In this tutorial, I follow the steps that I described in the How to Compute Time Complexity of Recursive Algorithms Tutorial. So, you may first need to read and study that one.

Our goal is to compute the time complexity of a recursive factorial algorithm. We are given the C/C++ code below:

 

int factorial(int n)

{

†† if(n >0) /* the most likely case, so I write this first */

†† {

††††† return n*factorial(n-1);

†† }

†† else† if ( n==0)

†† {

††††† return 1;

†† }

†† else /* n<0, the least likely case */

†† {

††††† return -1;

†† }

}

The question is what the time complexity of this algorithm is? In other words, ďour goal is to find the number of steps required to solve an n-element recursive problem.Ē For this specific example, we can focus on the number of multiplications. And, n does not refer to the number of the elements but simply the value of the input number. Remember that in the factorial problem we always have 1 element, so our focus is on the value of the input, but not the size. Let us start the following steps introduced in the How to Compute Time Complexity of Recursive Algorithms Tutorial.

Step1: Count

For small n values (e.g., 0, 1, 2, 3, 4), count how many steps you need to solve the problem. Then, describe the number of the steps using the Tn notation by considering the code given above.

Tn: Number of the steps required to solve the problem when the value of the input is n.

For n=0, (0!), we need to compute T0, there is actually no multiplication, so we need 0 multiplication: T0 = 0

For n=1, (1!), we need to compute T1, there is 1 multiplication (1*factorial(0)), so T1 = 1

For n=2, (2!), we need to compute T2, there are 2 multiplications (2*factorial(1), factorial(1)= 1*factorial(0)), so T2 = 2

For n=3, (3!), we need to compute T2, there are 3 multiplications (3*factorial(2), factorial(2)= 2*factorial(1), factorial(1)= 1*factorial(0)), so T3 = 3

Step2: Find Recurrence Relation

Recurrence relation is nothing but a simple way of defining Tn recursively. Namely, we try to find an equation defines the number of the steps required to solve an n-element (that is the value of the input for this problem) problem in terms of number of the steps required to solve the same problem with less than n elements. While we are counting above, we saw that the number of the steps increase just by 1. So, we can write

Tn = Tn-1 + 1

What does this mean? It looks scary but it has a very simple meaning: To calculate n!, you need 1 more step than you need for (n-1)!. For example, if we need 5 steps to calculate 5!, we will need 5+1 steps to calculate 6!.

Step3: Expand the Recurrence Relation

Expand the recurrence relation by replacing the term on the right side of the equation using the entire recurrence relation. Our ultimate goal is to understand how the recurrence relation changes when we expand it, which is Step 4.

Tn = Tn-1 + 1

Tn-1 = Tn-2 + 1

Tn = Tn-2 + 1 + 1

Tn = Tn-2 + 2

Expand one more time

Tn = Tn-2 + 2

Tn-2 = Tn-3 + 1

Tn = Tn-3 + 1 + 2

Tn = Tn-3 + 3

We kind of see a pattern here, so we stop expanding.

Step4: Find a Pattern While Expanding the Recurrence Relation

We try to understand how the recurrence relation changes when we expand it. Let us compare all our expansions:

Tn = Tn-1 + 1

Tn = Tn-2 + 2

Tn = Tn-3 + 3

there is a clear pattern among these 3 equations, and we can write a generic equation for all 3 as follows:

Tn = Tn-k +k

Step5: Verify the Pattern by Expanding the Recurrence Relation

We claim that the pattern is Tn = Tn-k +k , and we need to prove it by expanding it similar to the Step3. We have

Tn = Tn-k +k

On the right side of the equation, we have Tn-k and it is

Tn-k = Tn-k-1 + 1† (remember that Tn = Tn-1 +1)

and letís expand Tn = Tn-k +k

Tn = Tn-k +k = (Tn-k-1 +1) +k = Tn-k-1 + k+1

so what? we have

Tn = Tn-k-1 + k+1

Letís rewrite it

Tn = Tn-(k+1) + (k+1)

add some color

Tn = Tn-(k+1) + (k+1)

We here prove that Tn = Tn-k + k is also accurate for k+1. In other words, we proved it by mathematical induction. If you need to learn more about the mathematical induction, you can read and study Mathematical Induction Tutorial.

Step6: Write Tn ONLY in terms of n

Our goal is now to get rid of the parameter k in Tn = Tn-k + k so that we can find a definition of Tn only in terms of n. Why do we need such a definition? Because it will tell us how many steps we need to solve the recursive factorial problem when the value of the input is n. We know from the Step1 that

T0 = 0††††††††††††††††††

T1 = 1††††††††††††††††††

T2 = 2††††††††††††††††††

Therefore, instead of Tn-k, we want to have something like T0 or T1 or T2 on the right side of the recurrence equation. How can we transform Tn-k into T1?

n-k=1

n-1=k

so if k is n-1, we will have T1 on the right:

Tn = Tn-k +k

k = n-1

Tn = Tn-(n-1) +n - 1

Tn = T1 +n - 1†††††

We know that T1 = 1

Tn = 1 +n - 1

Tn = n

This means that if we have n elements in the problem, we need n steps to solve the problem. Accordingly, we can say that the time complexity of this problem is O(n) .

By the way, in the equation above, if you like, you can transform Tn-k into T0:

n-k=0

n =k

so if k is n, we will have T0 on the right:

Tn = Tn-k +k

k = n

Tn = Tn-n +n

Tn = T0 +n††††††††††††

We know that T0 = 0

Tn = 0 +n

Tn = n

This is the end of the tutorial. I hope you enjoyed it. Please feel free to contact me at haberdar AT gmail dot com. You can use anything here as long as you give credit as follows:
Hakan Haberdar, "Time Complexity of Recursive Factorial Algorithm", Computer Science Tutorials [online], (Accessed MM-DD-YYYY) Available from: http://www.haberdar.org/time-complexity-recursive-algorithms-tutorial.htmm