Space & amortized analysis

Every algorithm needs its input in memory, so counting the input says nothing about the algorithm. What tells two solutions apart is the auxiliary space: the extra memory they use on top of the input, as a function of n.

Take reversing a list of n items. One way builds a second list and fills it from the back: n extra cells, O(n) auxiliary space. The other swaps the first and last items, then the second and second-to-last, and so on toward the middle. It needs two position counters whatever the length: O(1).

An algorithm that works with O(1) extra space, changing its input directly, is said to work in place. In-place algorithms save memory, but they overwrite the input, so they only fit when the caller doesn't need the input afterward.

When people say an algorithm "uses O(n) space", they nearly always mean auxiliary space. If it matters, ask which one they mean.

Arrays & strings left a puzzle. Appending to a dynamic array is one write while there is spare capacity. When the block is full, the same append copies every item into a bigger block: O(n).

So what does an append cost? Saying O(n), the worst case for one append, is true but misleading: if you append a million items, almost none of the appends copy anything. What you really want to know is the cost of the whole sequence.

Follow eight appends into an array that starts with room for one item and doubles its capacity whenever it is full.

The block filled at 1, 2 and 4 items, and each time every item was copied: 1 + 2 + 4 = 7 copies for 8 appends.

The pattern holds at any size. The copies are 1 + 2 + 4 + … up to the last full block, and a sum of doubling numbers is always less than twice its last term. So n appends never make more than 2n copies, plus the n writes themselves. Fewer than 3n steps for n appends is a constant per append: O(1) amortized.

Any fixed multiple works the same way. A factor of 1.5 copies a little more often than 2 but leaves less unused space, which is the trade real libraries choose between.

Growing by exactly as much as you need sounds thrifty. Run the same eight appends, but add one cell each time the block is full:

Now every append after the first copies everything: 1 + 2 + … + 7 = 28 copies, and n(n − 1) ÷ 2 in general. That is O(n²) for n appends, O(n) per append.

Adding 100 cells at a time doesn't fix it. It cuts the copies about a hundredfold, to roughly n² ÷ 200, but the growth is still quadratic. Only growing by a multiple of the current size keeps appends O(1) amortized.

Adding 1 to a binary counter flips every trailing 1 to 0 and the next 0 to 1. Going from 0111 to 1000 flips four bits, so one addition can cost O(bits). But the lowest bit flips on every addition, the next on every second, the next on every fourth: n additions flip fewer than 2n bits in total. O(1) amortized, the same argument as the doubling array.

The two are easy to mix up:

• an average case is an average over possible inputs, so a bad input can still be slow;
• an amortized cost is an average over a sequence of operations, and it holds for every input.

What amortized analysis doesn't promise is that every single operation is fast. The append that triggers a copy of a million items really does copy a million items. Usually nobody notices, but in code where one slow step matters, such as drawing a frame on time, that pause can be a problem.

When you know the final size, you can avoid the copies altogether by asking for the capacity up front: new ArrayList<>(n) in Java, v.reserve(n) in C++. Then every append is one write.

An array that grows should probably shrink once most of it is empty. The obvious rule, halving the capacity when it drops to half full, has a trap.

Picture a full block of 8 items. One append doubles it to 16 and copies 8. Remove that item and the array is half full again, so it halves to 8 and copies 8. Append again, and it doubles again. Each operation now copies n items, and an unlucky sequence costs O(n) per operation.

The fix is a gap between the two thresholds: double when full, but halve only when the array drops to a quarter full. After either resize the array is half full, so it takes many operations to reach either threshold again, and the amortized cost stays O(1).