Space Complexity

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 (written in pseudo-code, so they apply to any language):

Constant Space Complexity:

function add(a, b):
    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):
    numbers = empty list
    for i from 0 to n - 1:
        add i to the end of numbers
    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):
    numbers = empty list
    for i from 0 to n - 1:
        add an empty list to the end of numbers
        for j from 0 to n - 1:
            add j to the end of the row at index i
    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 its execution (without taking the input values into account).

Space Complexity = Auxiliary Space + Input space

Let's see some examples:

function addAll(arr):
    sum = 0
    for each num in 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).