Time complexity vs. space complexity (2024)

Space complexity

The space complexity of an algorithm is the amount of space (or memory) taken by the algorithm to run as a function of its input length, n. Space complexity includes both auxiliary space and space used by the input.

Auxiliary space is the temporary or extra space used by the algorithm while it is being executed. Space complexity of an algorithm is commonly expressed using Big O $(O(n))$(O(n)) notation.

Many algorithms have inputs that can vary in size, e.g., an array. In such cases, the space complexity will depend on the size of the input and hence, cannot be less that $O(n)$O(n) for an input of size $n$n. For fixed-size inputs, the complexity will be a constant $O(1)$O(1).