Wie ist die zeitliche Komplexität der Operation zum Hinzufügen eines Elements zu einem Wörterbuch?

In Wörterbüchern (zum Beispiel Dictionary in Swift) hat die Operation zum Hinzufügen eines Elements in der Regel eine amortisierte Laufzeitkomplexität von O(1). Dies wird durch die Verwendung von Hashtabellen erreicht, bei denen die Berechnung des Hashs des Schlüssels und das Einfügen im Durchschnitt in konstanter Zeit erfolgen. Im schlimmsten Fall, z.B. bei Kollisionen oder der Notwendigkeit, das interne Array zu erweitern, kann die Komplexität vorübergehend auf O(n) ansteigen, wobei n die Anzahl der Elemente im Wörterbuch ist.