Understanding space and time complexity - Part 1

Let’s say we have given JS code:

function sumOfSeq(n) {
  let sum = 0;
  for (i = 0; i < n; i++) {
    sum = sum + pairSum(i, i + 1);
  }
  return sum;
}

const pairSum = (a, b) => {
  return a + b;
};

console.log(sumOfSeq(5));

Time Complexity

The common mistake most do is to think because the outer function sumOfSeq is calling an inner function pairSum, and say both has time complexity of O(n), then we just need to simply multiply them together, i.e.,

\( O(n) * O(n) = O(n^2)\)

.

Which is wrong.

If you see the outer function, it has a for loop that runs n-1 times (we can take it as n).

So, outer function has time complexity of O(n).

The inner function is straight forward and it just accepts two variable a and b, and it returns the sum of them. It has no loop or any other conditional, hence its time complexity is o(1).

Space Complexity

For space complexity, we need to find if our function going to use some extra space in the memory. For outer function, it looks that for loop may need extra space but because its returning just a single variable, the for loop exists only when its executed and after that it got killed.

Hence space complexity of outer code is O(1) and similarly, its O(1) for inner one.

---