Space Complexity Examples#

Sum Array of Numbers#

Consider:

function sum(xs: number[]): number {
  let total = 0;

  for (let i = 0; i < xs.length; ++i)
    total += xs[i];

  return total;
}

This simple and humble algorithm takes space for total and i. When i is incremented or total is added to, the space does not change. There is time complexity increase, sure, but the space complexity remains the same. Incrementing a numeric variable doesn’t take more space. Therefore, this algorithm’s space complexity is O(1).

Sum Array Space Complexity

Double Array of Numbers#

function doubleNums(xs: number[]): number[] {
  const doubled: number[] = [];

  for (let i = 0; i < xs.length; ++i)
    doubled[i] = xs[i] * 2;

  return doubled;
}

export { doubleNums };

The doubled array starts empty, but gets longer and longer directly in proportion to the length of the input, which is significant! Incrementing i, however, is not significant for space complexity. It will always hold a number, no matter how large that number is. But the doubled array will keep storing more and more numbers.

Double Array of Numbers Space Complexity