Calculating the factorial of number recursively (Time and Space analysis)

“grayscale photo of wood trunks” by John Westrock on Unsplash

The factorial of a number is defined as:

f(n) = n * f(n-1) → for all n >0
f(0) = 1 → for n = 0

factorial(n):
    if n is 0
         return 1
    return n * factorial(n-1)

C++ code:

Time complexity

If we look at the pseudo-code again, added below for convenience. Then we notice that:

• factorial(0) is only comparison (1 unit of time)
• factorial(n) is 1 comparison, 1 multiplication, 1 subtraction and time for factorial(n-1)

factorial(n):
    if n is 0
         return 1
    return n * factorial(n-1)

From the above analysis we can write:

T(n) = T(n — 1) + 3
T(0) = 1

T(n) = T(n-1) + 3
     = T(n-2) + 6
     = T(n-3) + 9
     = T(n-4) + 12
     = ...
     = T(n-k) + 3k
as we know T(0) = 1
we need to find the value of k for which n - k = 0, k = n
T(n) = T(0) + 3n , k = n
     = 1 + 3n
that gives us a time complexity of O(n)

Space complexity

For every call to the recursive function, the state is saved onto the call stack, till the value is computed and returned to the called function.

Here we don’t assign an explicit stack, but an implicit call stack is maintained

f(6) → f(5) → f(4) → f(3) → f(2) → f(1) → f(0)
f(6) → f(5) → f(4) → f(3) → f(2) → f(1)
f(6) → f(5) → f(4) → f(3) → f(2)
f(6) → f(5) → f(4) → f(3)
f(6) → f(5) → f(4)
f(6) → f(5)
f(6)

The function in bold is the one currently being executed. As you can see for f(6) a stack of 6 is required till the call is made to f(0) and a value is finally computed. Hence for factorial of N, a stack of size N will be implicitly allocated for storing the state of the function calls.

The space complexity of recursive factorial implementation is O(n)

If you like the post and want to learn more about Data Structures and Algorithms, Low-Level Design and High-Level Design to crack top product company interviews and get into FAANG, then I would highly recommend joining Scaler, where I am an Alumni and owe a lot of my success to them. Their curriculum is highly structured with teachers who are ex-Googlers, ex-Media.net etc. employees. You also get mentorship from the very best, working in your dream tech companies like FAANG. If you use the link my link to join Scaler, then you will get a course discount of Rs. 10,000 and I will get a cashback of the same amount. Do check out their course and take advantage of the classes provided by them to boost your career from the comfort of your home.

For more coding related tips and walkthroughs check out my content. Happy coding !!