What to hand in

algo with history and queue, passing go test ./..., plus a measurement table.

1. The quadratic curve

Measure copy-down shifts for n = 1,000 … 200,000:

n	shifts	shifts ÷ n²

The last column should be nearly constant (~0.5). Explain why.

2. The leak threshold

Step 3 showed 7,034 KB at n = 100,000.

Find the smallest n for which the leak exceeds 1 MB. Then work out how many bytes one Item occupies, and check your prediction against the measurement.

3. What the ring costs

A ring buffer requires knowing the size in advance.

Measure the memory a Ring sized for 100,000 uses when the queue holds 10 on average. Compare with the q[1:] approach doing the same work. Which is worse, and when?

4. Bounded undo

Real programs do not keep undo history forever. Give History a maximum: at max, the oldest entry is discarded.

Which end do you discard from? Implement it and count the cost. If your answer is O(n), reread lesson 3's rule and propose a structure that does it more cheaply.

5. The decision

One paragraph: for your "up next" queue — q[1:], copy-down or a ring?

Justify with the numbers from parts 1 and 3. State the queue size and usage rhythm you are assuming — because the answer depends on them, and there is no correct answer without them.