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

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.