Care este complexitatea temporală a operației de inserare a unui nou element într-un array?

Inserarea unui element nou într-un array are o complexitate temporară de O(n) în cel mai rău caz, unde n este numărul de elemente din array.

Motivul este că array-ul are o dimensiune fixă, iar pentru a insera un element în mijloc sau la început, trebuie să deplasați toate elementele ulterioare cu o poziție spre dreapta. Dacă inserția are loc la sfârșit și există spațiu liber, operația poate fi O(1).

Exemplu:

• Inserție la sfârșit cu spațiu disponibil: O(1)
• Inserție la început sau în mijloc: O(n) din cauza deplasării elementelor

În array-urile dinamice (de exemplu, ArrayList în Java), atunci când array-ul se umple, se face o copiere într-un array nou de dimensiune mai mare, ceea ce necesită, de asemenea, O(n) timp.