0

I got this problem to calculate the time complexity?

const iterate = a => {
  if (a === 5) {
    return;
  }
  for (var i = 0; i <= a; i++) {
    console.log(i);
    iterate(i + 1);
  }
};
iterate(0);
Neeraj Mishra
  • 9
  • 1
  • Possible duplicate of [How to measure time taken by a function to execute](https://stackoverflow.com/questions/313893/how-to-measure-time-taken-by-a-function-to-execute) – Wimanicesir May 09 '19 at 08:26
  • Time complexity here is just infinite, because `var i` is always set to 0, so it's an endless loop. – briosheje May 09 '19 at 08:45
  • 1
    @Wimanicesir time complexity is not (strictly) just timing the execution. You *could* measure the execution time for few different values of `n` and try to derive the big-O complexity but that's only one way to do that, not *the* way to measure time complexity. – VLAZ May 09 '19 at 08:59
  • @VLAZ "In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm." He wanted to calculated 'this code'. So the linked SO will suffice. – Wimanicesir May 09 '19 at 09:05
  • 1
    @Wimanicesir time complexity is about the *growth rate* not the literal execution time. Let's say you are operating on an array and it can contain any amount of items. We'll dub this amount `n`, so the *time complexity* of the algorithm would describe how the execution time varies based on `n` - if it takes 10ms for `n=1`, 20ms for `n=2`, 100ms for `n=10` and so on, that's a linear increase, so it's a `O(n)` complexity. If the timings are instead 10ms, 40ms, 1000ms, then that's a quadratic increase - `O(n^2)`. It's rarely so clear cut but big-O notation is concerned with the trend, not timings – VLAZ May 09 '19 at 10:30
  • 1
    @Wimanicesir and indeed, time complexity is *calculated*, because it's a mathematical analysis of the algorithm itself. As in, the actual steps the code makes. It isn't "calculating" as in using a stopwatch to determine the time something takes. – VLAZ May 09 '19 at 10:32

2 Answers2

1

You get an infinite loop, because you increment the target value by one, but you start the for statement with zero and this value does not change until it reaches the end of stack.

for (var i = 0; i <= a; i++) {
    console.log(i);
    iterate(i + 1);
}

That means, with the first zero value, you call the function again and this function calls itself again and so on.

The result is this uncatched error:

RangeError: Maximum call stack size exceeded
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
0

Algorithm complexity is only defined for algorithms, which by (the most often accepted) definition must terminate.

The code above iterates for infinite number of times. So the time complexity of the code cannot be determined.

One may say O(n) where n=> infinity.

The above code doesnt stop since there is not condition on the value of 'i' which increases upto infinity.

Naga Raj
  • 68
  • 7
  • how to calculate it? – Neeraj Mishra May 10 '19 at 11:18
  • 1) O(1): Time complexity of a function (or set of statements) is considered as O(1) if it doesn’t contain loop, recursion and call to any other non-constant time function. 2) O(n): Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount. 3) O(n^c): Time complexity of nested loops is equal to the number of times the innermost statement is executed where c= number of nested loops. Since your function runs infinitely with recursion but there are no nested loops . Hence it is in the order of n. – Naga Raj May 13 '19 at 09:49