Wat is de tijdcomplexiteit van de operatie om een nieuw element in een array in te voegen?

Het invoegen van een nieuw element in een array heeft in het slechtste geval een tijdcomplexiteit van O(n), waarbij n het aantal elementen in de array is.

De reden is dat de array een vaste grootte heeft, en om een element in het midden of aan het begin in te voegen, moeten alle volgende elementen één positie naar rechts worden verschoven. Als de invoeging aan het einde plaatsvindt en er is ruimte, kan de operatie O(1) zijn.

Voorbeeld:

• Invoegen aan het einde met beschikbare ruimte: O(1)
• Invoegen aan het begin of in het midden: O(n) vanwege het verschuiven van elementen

Bij dynamische arrays (bijvoorbeeld, ArrayList in Java), wordt bij overloop van de array een kopie gemaakt naar een nieuwe array met een grotere grootte, wat ook O(n) tijd vereist.