Wie ist die zeitliche Komplexität der Operation zum Hinzufügen eines Elements am Anfang eines Arrays?

Das Hinzufügen eines Elements am Anfang eines Arrays hat in der Regel eine Zeitkomplexität von O(n), wobei n die Anzahl der Elemente im Array ist.

Dies liegt daran, dass beim Einfügen am Anfang alle bestehenden Elemente nach rechts verschoben werden müssen, um Platz für das neue Element zu schaffen. Bei dynamischen Arrays (z.B. Swift Array) erfordert dieser Vorgang das Kopieren oder Verschieben von Elementen, was zeitlich proportional zur Anzahl der Elemente ist.

Beispiel:

var array = [2, 3, 4]
array.insert(1, at: 0) // fügt 1 am Anfang ein
print(array) // [1, 2, 3, 4]

Hier werden beim Einfügen von 1 alle Elemente um eine Position nach rechts verschoben.