Big-O's Cousins, Part 2: Space Complexity — Why the Fastest Algorithm Isn't Always the Right One
Big-O usually gets used to describe how long an algorithm takes -- the exact same notation also describes how much memory it needs, and the two don't always point the same direction.
Imagine two ways to move apartments: hire a crew that finishes in one fast afternoon but needs three moving trucks parked outside, or hire a slower crew that takes two full days but fits everything into a single car, making repeated trips. Both get the job done; they're trading time against how much space they need to have available at once. Algorithms make that exact same trade, and space complexity is the half of that trade Big-O notation almost never gets used to describe, even though the notation itself works identically for it.
Space complexity measures how much additional memory an algorithm needs as its input grows, using the exact same Big-O, Big-Omega, and Big-Theta notation already covered in this category's time-complexity pieces -- O(1) means constant extra memory no matter how large the input gets, O(n) means memory use grows in direct proportion to the input, and so on. It's describing a completely different resource than time complexity, using the same mathematical vocabulary to do it.
Merge sort and quicksort make this trade concretely: both sort in roughly the same O(n log n) time on average, but merge sort needs a separate O(n) block of extra memory to merge sorted halves back together, while quicksort sorts in place, needing only O(log n) extra space for its recursive call stack. Merge sort's guaranteed worst-case time makes it attractive in theory; its extra memory requirement is a real, practical reason quicksort variants are more commonly used in general-purpose sorting libraries.
This isn't a purely academic distinction: an algorithm with excellent time complexity that also needs memory proportional to a very large input can simply fail outright on a memory-constrained device -- an embedded system, a mobile app, a machine already under memory pressure -- in a way a slightly slower, more memory-frugal algorithm never would. The "fastest" algorithm on paper is only actually usable if its memory requirement fits the machine it has to run on.
Reading an algorithm's performance from its time complexity alone is reading half the actual cost -- exactly like judging a moving job purely on how many hours it takes, without ever asking how many trucks have to be parked outside to pull it off. A genuinely complete picture of an algorithm's cost accounts for both dimensions together, since a real system is limited by whichever one runs out first.