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

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