A Common-Sense Guide to Data Structures and Algorithms

Big O Notation as Applied to Space Complexity

Interestingly, computer scientists use Big O Notation to describe space complexity just as they do to describe time complexity.

Until now, we’ve used Big O Notation to describe an algorithm’s speed as follows: for N elements of data, an algorithm takes a relative number of operational steps. For example, O(N) means that for N data elements, the algorithm takes N steps. And O(N²) means that for N data elements, the algorithm takes N² steps.

Big O can similarly be used to describe how much space an algorithm takes up: for N elements of data, an algorithm consumes a relative number of additional data elements in memory. Let’s take a simple example.

Let’s say that we’re writing a JavaScript function ...