Premium

Space Complexity

Basic Algorithms
≈ 2 min read

An algorithm spends more than time

Space complexity shows how the amount of memory required by an algorithm changes as the input grows. It is often especially useful to look separately at auxiliary space — what the solution creates in addition to the input it was given.

If an algorithm needs only a few variables regardless of the array length, the additional memory stays constant: 

int max = numbers[0];

for (int value : numbers) {
    if (value > max) {
        max = value;
    }
}

The max variable occupies a fixed amount of memory, so the auxiliary space complexity of this solution is O(1).

A new structure as large as the input

If a solution creates a new array whose size depends on n, the memory usage grows together with the input. 

int[] doubled = new int[numbers.length];

for (int i = 0; i < numbers.length; i++) {
    doubled[i] = numbers[i] * 2;
}

For n original elements, another n values are created, so the auxiliary space is on the order of O(n).

Stack memory counts too

Additional memory is not limited to arrays, collections, and objects explicitly created with new. Every active method call stores data for that call on the stack. Therefore, deep recursion can also increase space complexity, even if the method does not create large data structures itself.

When analyzing a solution, it helps to ask a simple question: if the input becomes ten times larger, will the algorithm need roughly the same amount of extra memory, ten times more, or will the amount barely change?

Be clear about what you are measuring. Total memory includes the input data, while auxiliary space complexity counts only memory used by the algorithm beyond the input. Problems most often compare the latter.
Back Next