Kokia yra naujo elemento įterpimo į masyvą operacijos laiko sudėtingumas?

Įterpti naują elementą į masyvą blogiausiu atveju turi laiko sudėtingumą O(n), kur n yra elementų skaičius masyve.

Priežastis ta, kad masyvas turi fiksuotą dydį, ir norint įterpti elementą viduryje arba pradžioje, reikia perkelti visus vėlesnius elementus vieną poziciją į dešinę. Jei įterpimas vyksta pabaigoje ir yra laisva vieta, operacija gali būti O(1).

Pavyzdys:

• Įterpti į pabaigą su laisva vieta: O(1)
• Įterpti į pradžią arba vidurį: O(n) dėl elementų perkėlimo

Dinamiškuose masyvuose (pvz., Java ArrayList), kai masyvas užpildomas, jis kopijuojamas į naują didesnį masyvą, kas taip pat reikalauja O(n) laiko.