What is the Big O difference for iterative vs recursive?

Question

What is the Big O difference for iterative vs recursive? And why are the run times so different. I would assume O(n) as it has one loop for the iterative.

Here is a medium article with a nice graph.

function factorial (n) {
  if( n === 0 || n === 1 ) {
    return 1;
  }
  let prev = 1;
  let ret;
  while(n >= 2) {
    ret = prev * n;
    prev = ret;
    n--;
  }
  return ret;
}

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

The recursive version seems to take significantly longer. See SO Q/A here..

CertainPerformance · Answer 1 · 2019-07-28T00:11:12.240

1

Yes, those functions both have O(n) computational complexity, where n is the number passed to the initial function call.

The first function executes the (O(1) complexity) statements in the while loop for every value between a larger n and 2, for an overall complexity of O(n).

The second function recursively calls itself n times, without any loops, for (again) an overall complexity of O(n).

If you wanted to reduce the computational complexity for multiple calls of the functions, I'd create a lookup table to save the values calculated from previous calls, resulting in m calls of the function running in O(n) (where n is the highest number ever passed), rather than m calls running in O(n * m) (or O(n^2)) time.

If

The recursive version seems to take significantly longer.

this is not due to computational complexity, but due to how the compiler works with the different approaches. Function calls generally have more of an overhead than a simple while loop (though, this sort of optimization is almost never something to worry about in real life - code readability and maintainability is more important most of the time).

edited Jul 28 '19 at 00:11

answered Jul 28 '19 at 00:04

CertainPerformance

356,069
52
309
320

Thanks, I kind of got that already. The question was more .... why is the time so different for the same `n` ... 5ms compared to 150ms and how can this be captured in Big O or can it not be. – jakob dennison Jul 28 '19 at 00:11
If you're referring to Gabriele Petrioli's answer, that part is pretty misleading - he's using `Date.now` (which is not very precise) *and* is only running a relatively small number of iterations (compared to a real performance test). It also looks to be inaccurate, I'm getting 3-5ms vs 10-15ms here: https://jsfiddle.net/s7ue6gtq/ in the latest version of Chrome. But 5ms vs 150ms is *possible*, even with the same computational complexity (given the overhead of a function call is). – CertainPerformance Jul 28 '19 at 00:16
Does JavaScript have tail call optimization? – laptou Jul 28 '19 at 05:32
1

@laptou It's *supposed* to https://stackoverflow.com/questions/37224520/are-functions-in-javascript-tail-call-optimized but very few environments have implemented it yet, unfortunately – CertainPerformance Jul 28 '19 at 05:33
So you could say that it is O(n) for both except the constant is much greater for the recursive calls? – jakob dennison Jul 30 '19 at 01:06
@jakobdennison Exactly. If you did 1e20 tests for both approaches, maybe each would take something *around* 1e17 ms to complete - if their Big O was different, eg if one was `O(n^2)`, that one might take something like 1e34 ms to complete instead. The huge difference is visible with huge inputs. – CertainPerformance Jul 30 '19 at 01:13

What is the Big O difference for iterative vs recursive?

1 Answers1