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

Question

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.

You are passing just once in the function for each number, it is linear. — Nicolas, Feb 05 '20 at 15:56
They are both linear in Big O. Which do you think is more efficient if you take the constants into consideration? — jennifer, Feb 05 '20 at 16:08
Given that the latter function is tail recursive, the compiler will probably optimize it to a loop anyway. So it's a toss-up efficiency wise. You can use a site like http://jsben.ch/ to compare the two implementations; I just did and the speed is roughly the same in Chrome. — benbotto, Feb 05 '20 at 16:13
What do you mean tail recursive. The tail refers to what exactly? — jennifer, Feb 05 '20 at 16:15
In a nutshell it just means that the last call in the function is a call to itself. https://en.wikipedia.org/wiki/Tail_call There's a section in there about converting a tail-recursive function to a loop. — benbotto, Feb 05 '20 at 16:20

score 7 · Accepted Answer · answered Feb 05 '20 at 15:59

7

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.

answered Feb 05 '20 at 15:59

technophyle

7,972
6
29
50

They are both linear in Big O. Which do you think is more efficient if you take the constants into consideration? – jennifer Feb 05 '20 at 16:04
The good old "for" is better of course. The second one does the multiple operations of PUSH, POP of the method, so it's not as efficient as the first one. Often, smaller code means more inefficiency. Especially, recursive functions are (almost always) inefficient, as much as they look so concise and beautiful. – technophyle Feb 05 '20 at 16:11
Sorry, no, I mean push/pop of the function into memory stack. – technophyle Feb 05 '20 at 16:15
1

I don't think that's quite accurate, @technophyle, and a quick benchmark will show the two are about equal. Tail recursion is easily convertable to a loop, and any half-baked compiler will optimize tail recursion out. – benbotto Feb 05 '20 at 16:15
@avejidah with this example, I agree it will be almost equal. – technophyle Feb 05 '20 at 16:16
... he is assuming that it is not optimized for academic purposes ... if it was not optimized creating the function stack would be costly as opposed to a for loop ... this is what you meant correct ? – jennifer Feb 05 '20 at 16:16
Sure then. If it's not optimized obviously the loop will be more efficient. You could further optimize by using a simple while loop and doing away with the `i` variable. – benbotto Feb 05 '20 at 16:18
yeah, I mean recursive functions can be optimized to a loop in almost all cases. performance-wise, memory use-wise. – technophyle Feb 05 '20 at 16:19
To sum up a "loop iteration" is faster than a "function iteration" b.c. of the function stack, but this is academic as most compilers will optimize to a loop ? – jennifer Feb 05 '20 at 16:20
Yeah, I think that's accurate @j.a. But to be pedantic, most compilers will optimize tail recursion, not necessarily recursion in general. – benbotto Feb 05 '20 at 16:22
According to this link ... https://www.geeksforgeeks.org/tail-recursion/ ... my recursive version is not tail recursion ... it uses factorial explicit as an example a few pages down. – jennifer Feb 05 '20 at 17:21
It's a rabbit hole ... adding another parameter to make it tail recursive takes away from the "aestheticness"" of recursion. If you want efficiency use iterative and get rid of extra variable. – jennifer Feb 05 '20 at 17:23

score 1 · Answer 2 · answered Feb 05 '20 at 16:13

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

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

2 Answers2