CODEWITHSUNDEEP
javascriptbig-o
jakob dennison
jakob dennison

Reputation: 13

What is the Big O difference for iterative vs recursive?

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

Upvotes: 0

Views: 626

Answers (1)

CertainPerformance
CertainPerformance

Reputation: 370779

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).

Upvotes: 1

Related Questions