Ποια είναι η χρονική πολυπλοκότητα της λειτουργίας προσθήκης ενός στοιχείου σε ένα λεξικό;

Στα λεξικά (για παράδειγμα, το Dictionary στο Swift), η λειτουργία προσθήκης ενός στοιχείου έχει συνήθως μια μέση χρονική πολυπλοκότητα O(1). Αυτό επιτυγχάνεται με τη χρήση κατακερματιστικών πινάκων, όπου ο υπολογισμός του κατακερματισμού του κλειδιού και η εισαγωγή πραγματοποιούνται σε σταθερό χρόνο κατά μέσο όρο. Ωστόσο, στην χειρότερη περίπτωση, π.χ., σε συγκρούσεις ή ανάγκη επέκτασης του εσωτερικού πίνακα, η πολυπλοκότητα μπορεί προσωρινά να αυξηθεί έως και O(n), όπου n είναι ο αριθμός των στοιχείων στο λεξικό.