Appending to a dynamic array is O(1) amortised. Derive that, then defend it against someone who points out that a single append copies the whole array.
Dynamic array append is amortized O(1) because capacity doubling makes the resize copy costs form a geometric series below 2n over n appends, even though one individual append can still be O(n). Use this complexity analysis answer to show the decision, trade-off, and evidence rather than a memorised definition. It also connects amortised analysis to the point an interviewer is testing.
Answer
Short answer
Appending to a dynamic array is O(1) amortized, not O(1) worst case. Occasional resizes copy existing elements, but when capacity doubles those copies happen at sizes 1, 2, 4, 8 and so on, adding to less than 2n total copies over n appends.
In a strong complexity analysis answer, the defending an amortised bound detail should connect the decision to a visible consequence.
Was this answer helpful?
Likely follow-ups
- What happens to the bound if the array grows by a fixed 1,000 slots instead of doubling?
- Hash map lookup is O(1) expected. How is that a different claim from O(1) amortised?
- Give me an amortised argument for a monotonic stack scan.
- Subset-sum is NP-complete and you just described an O(nW) algorithm for it. Reconcile those.
Related questions
- The assistant wrote a working solution and the interviewer asks for its complexity and one input that breaks it. How do you verify code you did not write?mediumAlso on complexity-analysis and big-o5 min
- A nightly job took 40 minutes last month and takes two hours forty on twice the data. What do you conclude about its complexity, and what would you measure next?mediumAlso on complexity-analysis4 min
- Find the largest rectangle in a histogram in linear time, and tell me what the stack holds at every step.hardAlso on amortised-analysis5 min
- Return the maximum of every window of size k as it slides across the array. Why a deque, and what is the invariant?hardAlso on amortised-analysis5 min