Arrays and dynamic arrays

Contiguous memory → O(1) random access. Fixed size → grow by doubling.

The append problem

• Room left → write, O(1)
• Store full → allocate bigger, copy all, O(n)
• Grow by +1 → resize every time, O(n) per append
• Grow by ×2 → resizes get exponentially rarer

Amortized O(1)

Total copying over n appends is linear → $\frac{O(n)}{n} = O(1)$ per append.

Trace: 63 copies over 64 appends ≈ 1 each.

Copies per append: the sawtooth

Spikes at 1, 2, 4, 8, 16, 32 — twice as far apart each time.

Watch it fill and double

Costs

• Random access by index: O(1)
• Append: O(1) amortized
• Insert / delete at front or middle: O(n)
• Cache-friendly: contiguous memory

Takeaway

Cheap at the end and by index, expensive in the middle. That's the array — and the baseline every later structure reacts to.