Aká je časová zložitosť operácie vloženia nového prvku do poľa?

Vloženie nového prvku do poľa má v najhoršom prípade časovú zložitosť O(n), kde n je počet prvkov v poli.

Dôvodom je, že pole má pevný rozmer, a na vloženie prvku do stredu alebo na začiatok je potrebné posunúť všetky nasledujúce prvky o jednu pozíciu doprava. Ak sa vkladá na koniec a je voľné miesto, operácia môže byť O(1).

Príklad:

• Vloženie na koniec pri dostupnom mieste: O(1)
• Vloženie na začiatok alebo do stredu: O(n) kvôli posunu prvkov

V dynamických poliach (napríklad ArrayList v Jave) pri preplnení poľa dochádza ku kopírovaniu do nového poľa väčšej veľkosti, čo tiež vyžaduje čas O(n).