**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 T_{n} notation by considering the code given above.

T_{n}: 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 T_{0},
there is actually no multiplication, so we need 0 multiplication: T_{0} = 0

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

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

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

**Step2: Find Recurrence
Relation**

Recurrence relation is nothing but a simple way of
defining T_{n} 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

T** _{n}**
= T

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.

T** _{n}**
= T

T** _{n-1}** = T

T** _{n}**
= T

T** _{n}**
= T

Expand one more time

T** _{n}**
= T

T** _{n-2}** = T

T** _{n}**
= T

T** _{n}**
= T

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:

T** _{n}**
= T

T** _{n}**
= T

T** _{n}**
= T

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

T_{n}
= T_{n-k} +k

**Step5: Verify the
Pattern by Expanding the Recurrence Relation**

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

T_{n}
= T_{n-k} +k

On the right
side of the equation, we have T_{n-k} and it is

T_{n-k} = T_{n-k-1}
+ 1 (remember that T_{n} = T_{n-1} +1)

and let’s
expand T_{n} = T_{n-k} +k

T_{n}
= T_{n-k} +k = (T_{n-k-1} +1) +k = T_{n-k-1} +
k+1

so what? we have

T_{n}
= T_{n-k-1} + k+1

Let’s rewrite it

T_{n}
= T_{n-(k+1)} + (k+1)

add some color

T_{n}
= T_{n-(k+1)} + **(k+1)**

We here
prove that T_{n} = T_{n-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 T _{n }ONLY
in terms of n**

Our goal is now to get rid of the parameter k in T_{n} = T_{n-k} + k so
that we can find a definition of T_{n} 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

T_{0}
= 0

T_{1}
= 1

T_{2}
= 2

Therefore,
instead of T_{n-k}, we want to have
something like T_{0} or T_{1} or T_{2} on the right
side of the recurrence equation. How can we transform T_{n-k} into T_{1}?

n-k=1

n-1=k

so if k is n-1, we
will have T_{1} on the right:

T_{n}
= T_{n-k} +k

k = n-1

T_{n}
= T_{n-(n-1)} +n - 1

T_{n}
= T_{1} +n - 1

We know that
T_{1} = 1

T_{n}
= 1 +n - 1

**T _{n}
= 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 T_{n-k} into T_{0}:

n-k=0

n =k

so if k is n, we will
have T_{0} on the right:

T_{n}
= T_{n-k} +k

k = n

T_{n}
= T_{n-n} +n

T_{n}
= T_{0} +n

We know that
T_{0} = 0

T_{n}
= 0 +n

**T _{n}
= 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**