Find Factorial of a given number using Javascript

Subscribe to my newsletter and never miss my upcoming articles

This article is a part of series - Analysis of Algorithm's (Time and Space Complexity) using Javascript

Factorial of a given number

The factorial of a non-negative​ number,n, is computed as the product of all integers between 1 and n (both inclusive).

factorial(n)=n∗(n−1)∗...∗1

It can also be thought of as:

factorial(n)=n * factorial(n-1)

Note: The factorial of 0 is 1.

Recursive Approach

Algorithm :

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

Code:

I/P:

function factorial(n){
  // base case
  if(n ==0 || n==1){
    return 1;
  }else{
     return n * factorial(n-1)
  }
}

let n = 4;
let answer = factorial(n);
console.log('The factorial of " + n + " is " + answer);

O/P:

The factorial of 4 is 24

Time Complexity Analysis:

Lets calculate the time it takes to run the algo, If we look at the algorithm again, we notice that:

  • factorial(0) takes 1 unit of time => T(0) = 1
  • factorial(n) consists of 1 comparison, 1 multiplication, 1 substraction and time for factorial(n-1) => T(n) = T(n-1) + 3

From the above analysis , we have:

T(0) = 1

T(n) = T(n-1) + 3

So,

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 =>

n - k =0
k = n

T(n) = T(0) + 3k
          = 1 + 3(n)   // T(0)= 1, k = n

that gives us a time complexity of O(n)

Space Complexity Analysis :

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)

No Comments Yet