A dynamic array doubles capacity when full. Amortized cost of append?
Options
- O(n)
- O(log n)
- O(1) (Correct option)
- O(n²)
Answer
O(1)
Why
Most appends just use a free slot: O(1). When the array is full, it allocates double the space and copies everything: O(n) for that one append.
But copies happen only at sizes 1, 2, 4, 8, ... and they add up to less than 2n over n appends. Averaged over all appends, each costs O(1).
That average-over-many reasoning is called amortized analysis.
Remember
Rare expensive steps averaged over many cheap ones = amortized.