CODEWITHSUNDEEP
javascripttime-complexitybig-o
jennifer
jennifer

Reputation: 762

What is the Big O ( time complexity ) for factorial computations?

It is linear for the iterative version:

// O(n)
function factorial (n) {
  let ret = 1;
  for(let i = 2; i <= n; i++) {
    ret = ret * i;
  }
  return ret;
}

and it appears to be linear for the recursive version as well:

function factorialR (n) {
  if( n === 0 || n === 1 ) {
    return 1;
  } else {
    return n * factorialR(n - 1);
  }
}

Is it linear for the recursive version as well? Instead of a loop for each additional value it is just an additional function call.

Upvotes: 4

Views: 4290

Answers (2)

Abhishek Kumar
Abhishek Kumar

Reputation: 900

If your algorithm is recursive with b recursive calls per level and has L levels, the algorithm has roughly O(b^L ) complexity

but this is a only a rough upper bound. The actual complexity depends on what actions are done per level and whether pruning is possible

Credit : Stephen Halim

For even more indepth and complex recursive time complexity head over to here

Upvotes: 1

technophyle
technophyle

Reputation: 9149

Both of your functions have O(n) in time complexity.

The first one is straightforward.

The second one calls the recursive function one time in each iteration, so, it's O(n) as well.

Upvotes: 7

Related Questions