In welke situaties kan het toevoegen van een element aan het einde van een ArrayList een tijdcomplexiteit van O(n) hebben?

Het toevoegen van een element aan het einde van een ArrayList heeft meestal een geamortiseerde tijdscomplexiteit van O(1), maar in sommige gevallen kan het O(n) zijn. Dit gebeurt wanneer de interne array die de elementen opslaat vol is en moet worden uitgebreid.

Bij het toevoegen van een nieuw element:

• Als er ruimte is, wordt het element gewoon toegevoegd — O(1).
• Als er geen ruimte is, wordt een nieuwe array van grotere grootte gemaakt (meestal 1,5-2 keer groter), en alle bestaande elementen worden gekopieerd naar de nieuwe array — deze operatie is O(n).

Dus, het toevoegen van een element kan precies op het moment van het uitbreiden van de interne array een tijdscomplexiteit van O(n) hebben.