What we talked about previously was measuring the time complexity of an algorithm. That's what we would do to measure how performant an algorithm is in terms of how fast it would execute. There's another side that we might be interested in though, and that is how much memory a solution might take.

There are a few things we should remember (at least in JavaScript) when measuring space complexity:

  • Most primitives (booleans, numbers, etc.) are constant space.
  • Strings require O(n) space where n is the string length. It takes more space as the longer the string is.
  • Reference types (arrays and objects... yes arrays in JavaScript are reference types too) are generally O(n) where n is the length of the array or the number of keys in an object.

Let's take the first example we had in our previous blog post, the function with O(n) time complexity:

function sumOfOneTo(n) {
  let total = 0;

  for (let index = 0; index <= n; index++) {
    total += index;
  }

  return total;
}

If we count the number of declarations here, we only have 2 (total and index variables). As those 2 variables are primitive types, and the fact that their value remains a primitive type throughout the whole function, the space complexity of this function is O(1) space. Again, we're using just looking at the big picture, cutting down the value from 2 to 1.

Here's an example of a function that is O(n) space:

function doubleArray(arr) {
  let newArray = [];

  for (let index = 0; index < arr.length; index++) {
    newArray.push(arr[index] * 2);
  }

  return newArray;
}

As we stated above, reference types (which includes arrays) have a O(n) complexity, where n is the size of the array. The function above modifies the length of the array based on the size of the array passed to the function's parameters.