Back to Study Material Data Structures and Algorithms

Space Complexity

Space complexity measures the total amount of memory an algorithm needs as a function of its input size. Like time complexity, it uses Big O notation and d...

Space Complexity

Accounting for Memory Usage in Algorithm Design

Space complexity measures the total amount of memory an algorithm needs as a function of its input size. Like time complexity, it uses Big O notation and describes how memory usage scales, not the absolute number of bytes consumed.

Space complexity has two components. The first is input space, the memory occupied by the input data itself. The second is auxiliary space, the extra memory the algorithm allocates beyond the input, such as temporary variables, recursion call stack frames, and additional data structures.

When people say an algorithm runs in O(1) space, they typically mean O(1) auxiliary space; the input must still be stored somewhere. An in-place sorting algorithm like insertion sort rearranges the input array without allocating any additional array, so its auxiliary space is O(1). Merge sort, by contrast, requires an auxiliary array of size n to merge subarrays, giving O(n) auxiliary space.

Recursion consumes stack space. Each recursive call pushes a new frame onto the call stack containing local variables and the return address. A recursive algorithm that calls itself n times deep uses O(n) stack space even if no other memory is allocated. For very deep inputs, this can cause a stack overflow. Tail-recursive algorithms, where the recursive call is the last operation in the function, can be optimized by compilers to reuse the current stack frame, reducing recursion to O(1) space, though not all languages support this optimization.

There is often a time-space trade-off: you can make an algorithm faster by consuming more memory, or reduce memory use at the cost of speed. Dynamic programming memoization stores computed results to avoid redundant work, exchanging O(n) space for a dramatic reduction in time. Hash tables consume O(n) space to provide O(1) average lookups instead of O(n) lookup time.

Worked example: reversing a string. An approach that allocates a new string of the same length and fills it from back to front uses O(n) auxiliary space. An in-place approach using two pointers that swap characters from the ends toward the middle uses O(1) auxiliary space. Both are O(n) in time, but the in-place version is more memory-efficient.

Interview tip: after giving a solution, mention both time and space complexity. If your solution uses O(n) space, proactively ask whether the interviewer would like a more space-efficient version. This demonstrates awareness of trade-offs.