Каква е времевата сложност на операцията за вмъкване на нов елемент в масив?

Добавянето на нов елемент към масив има времева сложност O(n) в най-лошия случай, където n е броят на елементите в масива.

Причината е, че масивът има фиксиран размер, и за да добавите елемент в средата или в началото, трябва да преместите всички следващи елементи с една позиция надясно. Ако добавянето става в края и има свободно място, операцията може да бъде O(1).

Пример:

• Добавяне в края при налично място: O(1)
• Добавяне в началото или в средата: O(n) поради преместването на елементите

В динамичните масиви (например, ArrayList в Java), когато масивът се запълни, се извършва копиране в нов масив с по-голям размер, което също изисква време O(n).