What is amortized time complexity for appending to a dynamic array?
PICTURE THIS: ARRAY IN MEMORY
Index starts at 0. Scan once for max — O(n).
Simple meaning
A geometric resize (double the capacity) copies O(n) elements only occasionally.
WHY — Complexity instead of guessing?
Why interviewers care about Complexity:
who only read docs from people who shipped.
and tied to DSA work.
Name the idea, why it exists, then one short example.
End with when you use it and one common pitfall.
STEPS — What happens step by step?
Before you speak the answer, walk the interviewer through these steps:
- 1A geometric resize (double
the capacity) copies O(n) elements only occasionally.
- 2Over n appends the
total copy work is O(n), so each append is amortized O(1) even though a single append can be O(n).
- 3Mention that a +1
resize policy would be amortized O(n) and is a bad design.
- 4Give an example
One tiny concrete case you can say aloud.
- 5Common mistake
What juniors usually get wrong.
- 6Close
When you pick this over the alternative.
EXAMPLE — See it in action
Here's a short line you can speak, broken into clear beats:
Note: Adapt this scaffold to your own project — keep it under 60–90 seconds.
Key takeaway
A geometric resize (double the capacity) copies O(n) elements only occasionally. Over n appends the total copy work is O(n), so each append is amortized O(1) even though a single append can be O(n).