Wat is de tijdcomplexiteit van de bewerking om een element in het midden van een array te plaatsen, geïmplementeerd via ArrayList?

Het invoegen van een element in het midden van een array, geïmplementeerd via ArrayList, vereist dat alle volgende elementen naar rechts worden verschoven om plaats te maken voor het nieuwe element. Dit betekent dat de insertie-operatie een tijdscomplexiteit van O(n) heeft, waarbij n het aantal te verschuiven elementen is. In het ergste geval (invoegen aan het begin) worden bijna alle elementen van de array verschoven.