A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

Big O of Space Complexity

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

Back when I introduced Big O notation in Chapter 3, ​O Yes! Big O Notation​, I described Big O in terms of what I called the “key question.” For time complexity, the key question was this: if there are N data elements, how many steps will the algorithm take?

To use Big O for space complexity, we just need to reframe the key question. When it comes to memory consumption, the key question becomes if there are N data elements, how many units of memory will the algorithm consume?

Here’s a simple example.

Let’s say we’re writing a function that accepts an array of strings and returns an array of those ...