Cheap on average
A growing list doubles its space now and then, and the copying still averages out to a little per item. About 9 minutes.
How a growing list works
Python lists, C++ vectors, Java ArrayLists and JavaScript arrays all keep spare space. It is like a bus that fills up: when it runs out of seats, everyone moves to a bus twice as big, and then the new bus has lots of empty seats again.
Copying everyone across is the expensive part. After it, appends are cheap again for a while.
- space
- 1
- copied
- 0
Space for 1. Append item 1: it fits.
Add it all up
Starting from space for 1 item, n appends copy 1 + 2 + 4 + … items, with each copy twice the last, and the final one smaller than n. That sum stays below 2n.
So a single append can be slow, but n appends cost O(n) together, which is O(1) each on average.
copies = 0
capacity = 1
while capacity < n:
copies += capacity
capacity *= 2
return copiesSpace starts at 1 and doubles when full. How many items are copied in total over 5 appends?
- A7
- B15
- C10
Show the answer
7. Appends 2, 3 and 5 find the space full and copy 1, 2 and 4 items.
Copies from doubling
A list starts with space for 1 item. Each append that finds the space full first doubles the space and copies every stored item into the new space. Return the total number of items copied over n appends.
n = 5 → 7
0 ≤ n ≤ 2,000,000,000 · return a long