A Common-Sense Guide to Data Structures and Algorithms

Chapter 14Dealing with Space Constraints

Throughout this book, when analyzing the efficiency of various algorithms, we’ve focused exclusively on their time complexity—that is, how fast they run. There are situations, however, where we need to measure algorithm efficiency by another measure known as space complexity, which is how much memory an algorithm consumes.

Space complexity becomes an important factor when memory is limited. This can happen when programming for small hardware devices that only contain a relatively small amount of memory or when dealing with very large amounts of data, which can quickly fill even large memory containers.

In a perfect world, we’d always use algorithms that are both quick and consume a small amount of memory. ...