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

Η χρονική πολυπλοκότητα της προσθήκης ενός νέου στοιχείου σε ένα λεξικό (π.χ., Dictionary σε Swift ή NSMutableDictionary σε Objective-C) είναι συνήθως O(1) κατά μέσο όρο. Αυτό οφείλεται στο γεγονός ότι το λεξικό υλοποιείται με βάση έναν πίνακα κατακερματισμού, όπου ο υπολογισμός του κατακερματισμού και η εισαγωγή πραγματοποιούνται σε σταθερό χρόνο.

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

Παράδειγμα σε Swift:

var dict = [String: Int]()
dict["key"] = 42 // Προσθήκη σε μέσο χρόνο O(1)