Hoe wordt de tijdcomplexiteit bepaald bij het toevoegen van een element aan ArrayList?

De tijdcomplexiteit van het toevoegen van een element aan ArrayList is meestal geamortiseerd O(1). Dit komt doordat:

• Als het interne array van ArrayList vrije ruimte heeft, wordt het nieuwe element gewoon op de volgende positie geschreven — de operatie kost constante tijd O(1).
• Als het interne array vol is, wordt het uitgebreid: er wordt een nieuw array met grotere grootte gemaakt en alle elementen worden daar naartoe gekopieerd. Deze operatie kost O(n), waarbij n de huidige grootte van de lijst is.

Echter, de uitbreiding gebeurt niet bij elke toevoeging, maar periodiek, dus de gemiddelde (geamortiseerde) complexiteit van toevoegen blijft O(1).

Voorbeeld:

ArrayList<Integer> list = new ArrayList<>();
list.add(10); // Geamortiseerd O(1)