Space Complexity measures the total amount of memory that an algorithm or operation needs to run according to its input size.

Space Complexity is a parallel concept to Time Complexity. We express space complexity measurements using the Big-O notation, following the same guidelines like we do for time complexity.

Now let's learn how to compute space complexity by taking a few examples:

Constant Space Complexity:

 function sum(a, b) {
    let sum = a + b;
    return sum;
}

In the example above, we use 3 number variables: a and b, which are input variables and sum, which is an auxiliary variable.

And because the space requirement is fixed (3 number variables), hence it is called Constant Space Complexity and is noted with O(1).

Linear Space Complexity:

 function generate(n) {
    let numbers = [];
    for (let i = 0; i < n; i++) {
        numbers.push(i);
    }
    return numbers;
}

In the example above, we use an auxiliary array numbers which is populated with n numbers.

Since the total space requirement is n numbers, the Space Complexity is increasing linearly with the increase in the input value n, hence it is called as Linear Space Complexity and is noted with O(n).

Quadratic Space Complexity:

 function generate(n) {
    let numbers = [];
    for (let i = 0; i < n; i++) {
        numbers.push([]);
        for (let j = 0; j < n; j++) {
            numbers[i].push(j);
        }
    }
    return numbers;
}

In the example above, we use an auxiliary 2D array numbers of n rows and n columns.

Since the total space requirement is n^2 numbers, the Space Complexity is directly proportional to the squared of the input value n, hence it is called as Quadratic Space Complexity and is noted with O(n^2).

Extra/Auxiliary Space:

Sometimes Extra/Auxiliary Space is confused with Space Complexity. But Auxiliary Space is the extra space or the temporary space used by the algorithm during it's execution (without taking the input values into account).

Space Complexity = Auxiliary Space + Input space

Let's see some examples:

 function sum(arr) {
    let sum = 0;
    for(let num of arr) {
        sum += num;
    }
    return sum;
}

In the example above, we have an input array arr. If we denote its length by n, the Input Space is O(n).

However, we use only 2 auxiliary variables sum and num, so the Extra Space is O(1).