Chapter 19
Dealing with Space Constraints

When analyzing the efficiency of various algorithms throughout this book, we’ve focused exclusively on how fast they run—that is, their time complexity. However, another measure of efficiency can be useful as well, which is how much memory an algorithm consumes. This measure is known as space complexity.

Space complexity becomes an important factor when memory is limited. If you have an enormous amount of data, or are programming for a small device with limited memory, space complexity can matter a lot.

In a perfect world, we’d always use algorithms that are both fast and memory-efficient. However, sometimes we can’t have both, and we need to choose between the two. Each situation requires a careful analysis to know when we need to prioritize speed over memory, and memory over speed.