Space Complexity

Definition

Time complexity asks how work grows with input size. Space complexity asks the equivalent question about memory.

The total memory an algorithm uses splits into two parts:

Total space = Input space + Auxiliary space

Input space is the memory needed to store the input itself. For the same input, this space is generally fixed regardless of the algorithm being used. When comparing the memory efficiency of algorithms, we therefore focus mainly on auxiliary space: the extra memory used by the algorithm beyond the input, for temporary variables, extra arrays, recursion, and so on.

Auxiliary space: O(1) example

sum = 0;
for (i = 0; i < n; i++)
    sum = sum + A[i];

A is the input array of size n, already counted as input space. Regardless of how large A is, this only ever needs one extra variable, sum, to accumulate the result. The auxiliary space does not grow with n, so it is O(1).

Auxiliary space: O(n) example

int B[n];
for (i = 0; i < n; i++)
    B[i] = A[i] * 2;

Here A is the input array of size n, already counted as input space. B is a new array, also of size n, created purely to hold the result. B is not part of the input, it is extra memory the algorithm allocates on top of it, so it grows in direct proportion to n, making the auxiliary space O(n).

Notice that in both this example and the O(1) example above, the input array itself is size n either way. The difference in space complexity comes entirely from what each algorithm allocates in addition to that input, sum (one variable) versus B (a whole new array), which is exactly what auxiliary space is measuring.

Why this matters alongside time complexity

An algorithm that is faster in time can sometimes only get there by using more memory, and vice versa. A classic example is trading memory for speed: storing precomputed results in an array (more space) to avoid recomputing them (less time). Neither time complexity nor space complexity alone tells the full story, which is why both are analyzed together under performance analysis.

Quick recall

• Space complexity measures memory as a function of input size n.
• Total space = input space + auxiliary space.
• Auxiliary space is the extra memory used beyond the input itself, and is what differs between algorithms solving the same problem.
• A constant number of extra variables gives O(1) auxiliary space; allocating a new structure that scales with n gives O(n).