An Intro to Space Complexity

A beginner’s guide to assessing an algorithm use of computer memory

What is space complexity?

Space complexity is a way to evaluate how efficiently an algorithm uses computer memory. Although we’re talking about memory — think ‘bytes’ — space complexity is expressed using big-O notation, i.e., how much additional memory is required based on input size.

You italicized ‘additional’ in ‘additional memory.’ Why?

Any new data structure created during the algorithm's execution is considered new data requiring new or additional memory. Yes, even if the data doesn’t persist beyond the execution of the algorithm. This additional space in memory is called auxiliary space.

Wait, before we go on…

What is Auxillary Space?

Auxiliary space is the extra space needed by an algorithm to execute.

Examples — What’s the space complexity of the following algorithm?

EXAMPLE 1

In the above example, we don’t need to allocate or copy any new data; we modify the given array. No additional data is required, even if the input array is large. Therefore, the space complexity is O(1) because we use a constant amount of space no matter the input size.

EXAMPLE 2

The first thing to notice is that this algorithm uses recursion. Why is this important? Well, every time we make a new function call a new stack frame to the stack memory. This means that if n is 100, then the recursion stack will be 100. Therefore, the space complexity is 0(n).

Can we write this refactor this algorithm to improve the space complexity?

With a loop:

This algorithm has O(1) space complexity because it uses a constant number of variables regardless of the input size.

Quadratically:

Using this quadratic algorithm, the space complexity is O(1), as no additional space is required.

Hopefully, this quick introduction to space complexity will help kickstart your journey to demystifying space, time complexity, and big-O notation.