Wat is de tijdcomplexiteit van de bewerking om een element aan het einde van een array toe te voegen met behulp van een slice?

In Go heeft de operatie om een element aan het einde van een slice (append) een geamortiseerde tijdcomplexiteit van O(1).

Uitleg:

• Als de slice voldoende capaciteit (capacity) heeft, wordt een element eenvoudigweg toegevoegd door te schrijven op de volgende vrije index — dit is een operatie in constante tijd.

• Als de capaciteit niet voldoende is, wordt een nieuw array met grotere grootte toegewezen, worden de oude elementen gekopieerd en wordt het nieuwe element toegevoegd — deze operatie kost O(n), waarbij n de huidige grootte van de slice is.

Omdat dergelijke herallocaties niet bij elke toevoeging plaatsvinden, maar slechts periodiek, blijft de gemiddelde (geamortiseerde) complexiteit van toevoegen O(1).