Kāda ir jauna elementa ievietošanas operācijas laika sarežģītība masīvā?

Ievietot jaunu elementu masīvā ir slēptā laika sarežģītība O(n) sliktākajā gadījumā, kur n ir elementu skaits masīvā.

Iemesls ir tas, ka masīvam ir fiksēts izmērs, un, lai ievietotu elementu vidū vai sākumā, ir nepieciešams pārvietot visus turpmākos elementus par vienu pozīciju pa labi. Ja ievietošana notiek beigās un ir brīva vieta, operācija var būt O(1).

Piemērs:

• Ievietošana beigās ar pieejamu vietu: O(1)
• Ievietošana sākumā vai vidū: O(n) elementu pārvietošanas dēļ

Dinamiski masīvi (piemēram, Java ArrayList) piepildoties, tiek veikta kopēšana uz jaunu lielāku masīvu, kas arī prasa O(n) laiku.