Wat is de tijdcomplexiteit van de bewerking om een element aan het einde van een ArrayList-achtig array toe te voegen?

De tijdscomplexiteit van het toevoegen van een element aan het einde van een ArrayList-achtig array gemiddeld is O(1) — geamortiseerde constante tijd.

Dit gebeurt omdat ArrayList de elementen opslaat in een vaste grootte array. Wanneer we een element toevoegen en er is ruimte in de array, wordt het element gewoon in de volgende cel geplaatst.

Echter, als de array vol is, wordt een uitbreidingsoperatie uitgevoerd — er wordt een nieuwe, grotere array gemaakt en alle elementen worden daarin gekopieerd. Deze operatie kost O(n) tijd, waarbij n het aantal elementen is.

Voorbeeld:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Wanneer de capaciteit van de array bereikt is, wordt er uitgebreid — O(n)

Dus, de gemiddelde complexiteit van toevoegen is — O(1), maar in het slechtste geval — O(n).