What is space complexity
In the last lesson we measured an algorithm's speed not in seconds but by how much its work grows as the input grows. Focusing on speed alone, though, it's easy to miss something. While an algorithm works, it does more than produce the answer: it jots notes, lays out spare slots, and builds tables. In other words, it spends room as well as time. One solution gets by with a single spot on the desk, while another, giving the very same answer, spreads out a whole second sheet. How do we measure that difference, and why does it matter?
The slots an algorithm uses besides the answer
Say we want the largest of six numbers. In the end the answer is a single number, but the way there depends on the solution. One solution writes the largest number seen so far on a single note and overwrites it whenever a bigger one comes along, so the note stays one sheet. A solution that writes each new largest number in a fresh slot uses more slots as it goes, and one that copies all the numbers over to arrange them from largest to smallest needs as many extra slots as the input. These scratch slots used while producing the answer are the cost in room. The input was handed to us anyway, so it doesn't count; we count only the slots the algorithm lays out on top of it.
The input (gold) was handed to us, so it isn't a cost. Turn on the temp slots to see the record (blue) this solution keeps by writing each new largest number in a new slot. Only these extra slots count as cost.
When measuring room, we leave out the input and look only at the extra slots, because that's what makes the comparison fair: for two solutions given the same input, we count only what each one uses on top. So is the solution that gets by with one note always better? If we save room, do we lose out somewhere else? Next comes the bargain between time and room.
More room, faster; less room, slower (the trade-off)
Even for the same problem, speed depends on how you use room. Suppose you need to look up some value often. One way is to compute every answer in advance and write them in a table. Each lookup is a single glance at the table, so it's very fast, but you have to set aside room for the table. Another way is to skip the table and recompute from scratch on every lookup. It takes almost no room, but it's slow because it repeats the same work each time. Giving up room to gain time, or giving up time to save room: this is the time-space trade-off.
Switch between spending more space and saving space. The side with a prebuilt table (blue) uses lots of room but is fast; the side that counts each time without a table (gold) saves room but is slow. Same problem, different bargain.
Neither side is always right; you choose based on the situation. If you'll ask often, building a table and spending the room pays off; if room is tight, solving without a table is better even if it's a little slower. So what does saving room look like in practice? For a common task like sorting, let's put side by side a solution that uses zero extra slots and one that uses a whole extra copy the size of the input.
Sorting in place vs making a copy
Say we want to line up scattered numbers from smallest to largest. One way is to tidy them by swapping pairs of numbers within the slots we were given. We don't make a single new slot; we only move things around inside the ones 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 there are inputs, then repeatedly pick the smallest remaining number and move it into the new slots. The result is the same sorted line, but we used a whole extra set of slots the size of the input. Both give the right answer, yet the cost in room is very different: zero, or the size of the input.
Choose sorting in place or making a copy, then run the sort. In place (gold) only swaps within the same slots, so the extra is 0; the copy (blue) makes new slots the size of the input. Same result, different cost in room.
In place, zero extra; a copy, as much as the input. The answer is the same, but the cost in room clearly differs. Doesn't "zero versus the size of the input" sound familiar? When we measured time in the last lesson, we also separated work that doesn't grow with the input from work that grows along with it. We can put that same lens on room. Next, we'll grow the input and watch how the extra room grows.
Room grows with the input too (O(1) or O(n))
In the last lesson, big O summed up in one symbol how time grows as the input grows. We use the same summary for room. The solution that finds the largest number with one note always has one extra slot, whether the input is six numbers or a hundred. However large the input gets, the extra room stays the same, so we call this O(1) space. The copying solution, on the other hand, doubles its new slots when the input doubles. Its extra room grows in direct proportion to the input, so this is O(n) space. With the same tool, big O, we're now measuring the shape in which room grows rather than time.
Grow the input to raise n. O(1) (gold) keeps just one extra slot however large the input gets, while O(n) (blue) grows right along with it. This is big O applied directly to room.
It's the same big O notation, but this time attached to room instead of time. O(1) means the extra room stays bounded by a small constant however large the input gets; O(n) means it grows alongside the input. Now we can look at an algorithm with two eyes: how long it takes, and how much room it uses. Time to pull the two together.
Summing up: a second eye for algorithms
Put in one line, it goes like this. While producing an answer, an algorithm uses temporary slots besides the answer itself, and those extra slots are its cost in room; the input isn't counted. Room and time are often traded: build a table in advance and use more room to go faster, or solve in place and save room but go slower. The extra room also grows with the input: always one slot is O(1), as much as the input is O(n). So when choosing a good algorithm, you can't look at speed alone. Only by weighing how fast it is together with how much room it uses can you choose well. On a small device with little memory, the slower solution that saves room is often the right one.
Press the four steps in order to string them into one line: the extra slots besides the answer, the room↔time trade-off, in place vs a copy, and room growing with the input (O(1)/O(n)). Space complexity fits on one panel.
Now we can measure an algorithm with two yardsticks at once: time and room. Among several solutions that give the same answer, we have an eye for judging which to choose in which situation. Putting not only speed but also the cost in room on the scale is what choosing an algorithm well really means. In the next lesson, with both yardsticks in hand, we'll go a step further into smarter ways of solving real problems.