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 ...
Get A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1 now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
