Een dynamische array reserveert, als er een element wordt toegevoegd terwijl hij vol is, een nieuw gebied met de dubbele capaciteit en kopieert alle elementen daarheen. Hoeveel elementkopieën worden er in totaal gemaakt als 1000 elementen één voor één worden toegevoegd aan een lege array met capaciteit 1?

Antwoord: B. 1023

De capaciteit verdubbelt telkens als de array vol is, van 1 naar 2, 4, …, 512, en elke keer worden alle aanwezige elementen gekopieerd, dus het totale aantal kopieën is 1 + 2 + 4 + … + 512 = 1023. Voor 1000 toevoegingen is dat ongeveer één kopie per element, dus de kosten per toevoeging zijn gemiddeld constant: geamortiseerd O(1). Zou de capaciteit telkens maar met 1 groeien, dan zouden de kopieën samen 1 + 2 + … + 999 = 499.500 bedragen, wat O(n²) is. 10 is het aantal keren dat opnieuw geheugen is gereserveerd, niet het aantal gekopieerde elementen.