Space Complexity: Room Costs Too
Last lesson we measured an algorithm's speed not in seconds but by how much its work grows as the input grows. But chasing speed alone, it is easy to miss one thing. While an algorithm works, it scribbles on scratch paper, lays out spare slots, builds tables, all beyond the answer itself. In other words, it does not only spend time; it spends room too. Is that room free? For the very same answer, one solution uses a single extra slot on the desk while another spreads out a whole second sheet. How do we measure that difference, and why should we care?
The Slots an Algorithm Uses Beyond the Answer
Say we want the largest of six numbers. The answer is, in the end, a single number. But while finding it, one solution keeps the largest seen so far on a single little note and rewrites it whenever a bigger number shows up. The note stays one sheet. Another solution copies all the numbers over once more in order to lay them out from largest to smallest. These scratch slots, jotted not as the answer itself but in the course of making it, are exactly the cost of room. The input we were handed anyway, so it does not count as cost; we count only the slots the algorithm spreads out on top.
The input (gold) was just handed to us. Tap turn on temp slots to see the slots (blue) the algorithm spreads out beyond the answer. Only these extra slots count as cost.
The key is that when measuring room, we leave out the input and look only at the extra slots. That is what lets us fairly compare two solutions given the same input. But think about it. Is the solution that gets by on one note always the better one? When we save room, might we lose out somewhere else? Next, let us look at the bargain between time and room.
More Room, Faster; Less Room, Slower (the Trade)
For the same problem, the speed changes with how you use room. Say you have to look up some value often. One way is to compute all the answers in advance and write them in a table. Each lookup is just one glance at the table, so it is very fast. In exchange, you must set aside room to hold that table. Another way is to skip the table and recompute from scratch on every lookup. It costs almost no room, but it is slow because it redoes the same work each time. Give up room to buy time, or give up time to save room. This is the time and space trade.
Tap spend more space and save space. The side with a prebuilt table (blue) uses much room and is fast; the side that counts each time (gold) saves room and is slow. Same problem, different bargain.
We saw that neither side is simply right; you choose by the situation. If you will ask often, building a table and spending room pays off; if room is tight, solving without a table is better even if a bit slow. But what does saving room concretely mean? On a common task like sorting, let us set side by side a solution that uses zero extra slots and one that uses a whole extra copy the size of the input.
Solving in Place vs Making a Copy
Say we line up scattered numbers from smallest to largest. One way is to tidy them by swapping the positions of two numbers within the slots we were given. We make not a single new slot; we only change positions inside the slots we have. This is called sorting in place, and the extra room is zero. Another way is to set up as many empty slots as the input has, then pick the smallest each time and move it into those new slots. The result is the same sorted line, but we used a whole extra set of slots, the size of the input. The extra room costs as much as the input. Both solutions give the right answer, but the cost of room differs greatly: zero, or the size of the input.
Choose sort in place or make a copy, then tap run the sort. In place (gold) just swaps within the same slots, extra 0; the copy (blue) makes new slots the size of the input. Same result, different cost of room.
In place, zero extra; a copy, the size of the input. Same answer, yet the cost of room clearly split. But this phrasing, zero versus the size of the input, does it not sound familiar? Last lesson, measuring time, we talked about what happens when the work does not grow as the input grows, and when it grows with the input. That very lens we can lay right onto room. Next, let us grow the input and watch how the extra room grows.
Room Grows with the Input, Too (O(1) or O(n))
Last lesson's big-O summed up, in one symbol, how time grows as the input grows. We use the very same summary for room. The solution that finds the largest on one note has an extra slot that stays one, whether the input is six or a hundred. However large the input, the extra room stays put, so we call this O(1) space. The copy-making solution, on the other hand, doubles its new slots when the input doubles. The extra room grows in direct proportion to the input, so this is O(n) space. The point is that with big-O, the same tool, we now measure the shape in which room grows, not time.
Tap grow the input to raise n. O(1) (gold) keeps just one extra slot however large the input; O(n) (blue) grows along with it. This is big-O applied straight to room.
The same big-O notation, but this time attached to room, not time. O(1) means the extra room is pinned to a small constant however large the input; O(n) means it grows right alongside the input. So now we see an algorithm with two eyes: how much time it takes, and how much room it uses. Let us pull these two together on one line.
In Summary: a Second Eye for Looking at Algorithms
Seen on one line, it goes like this. While producing the answer, an algorithm uses temporary slots beyond the answer. Those extra slots are the cost of room, and the input is left out of the cost. Room and time are often traded: build a table up front and spend more room to go faster, or solve in place and save room and go slower. And the extra room grows with the input too: always one slot is O(1), as much as the input is O(n). So when choosing a good algorithm, you cannot look at speed alone. How fast it is and how much room it uses, seen together with two eyes, is what finally lets you choose well. On a small device where memory is tight, the slow-but-room-saving solution is often the right answer.
Tap the four steps in order to thread them on one line. The extra slots beyond the answer, the room-and-time trade, in place vs a copy, and room growing with the input (O(1) or O(n)). Space complexity on one panel.
Now we can measure an algorithm by two yardsticks together, time and room. Among several solutions that give the same answer, we have gained an eye for judging which to choose in which situation. Putting not just speed but the cost of room on the scale is what finally amounts to choosing an algorithm like a grown-up. In the next lesson, carrying both yardsticks, we step a little further into smarter ways of solving real problems.