Welche zeitliche Komplexität hat die Operation zum Einfügen eines neuen Elements in ein Array?

Das Einfügen eines neuen Elements in ein Array hat im schlimmsten Fall eine Zeitkomplexität von O(n), wobei n die Anzahl der Elemente im Array ist.

Der Grund dafür ist, dass das Array eine feste Größe hat, und um ein Element in der Mitte oder am Anfang einzufügen, müssen alle nachfolgenden Elemente um eine Position nach rechts verschoben werden. Wenn die Einfügung am Ende erfolgt und Platz vorhanden ist, kann die Operation O(1) sein.

Beispiel:

• Einfügen am Ende bei verfügbarem Platz: O(1)
• Einfügen am Anfang oder in der Mitte: O(n) aufgrund des Verschiebens der Elemente

Bei dynamischen Arrays (z.B. ArrayList in Java) erfolgt beim Überlaufen des Arrays eine Kopie in ein neues Array mit größerer Größe, was ebenfalls O(n) Zeit erfordert.