Wat is de slechtste uitvoeringstijd van de add() methode voor ArrayList?

Geraamde constante tijd O(1).

In de meeste gevallen wordt add() uitgevoerd in constante tijd, omdat het nieuwe element eenvoudigweg wordt toegevoegd aan het einde van de bestaande interne array.

Het slechtste geval doet zich voor wanneer de capaciteit van de interne array wordt bereikt. In dat geval maakt ArrayList een nieuwe, grotere array (meestal 1,5 keer zo groot als de huidige), kopieert alle elementen van de oude array naar de nieuwe en voegt vervolgens het nieuwe element toe. Deze kopieeroperatie kost tijd die evenredig is aan het huidige aantal elementen (N), wat leidt tot een tijdcomplexiteit van O(N).

Echter, omdat dergelijke groottewijzigingen zelden voorkomen en over veel aanroepen van add() worden verdeeld, blijft de gemiddelde uitvoeringstijd van add() (geamortiseerd) constant.