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

Η εισαγωγή ενός στοιχείου στο μέσο μιας δομής δεδομένων που αντιπροσωπεύει ένα λεξικό εξαρτάται από την συγκεκριμένη υλοποίηση του λεξικού. Στα τυπικά λεξικά (π.χ., Dictionary στο Swift ή NSDictionary στο Objective-C), τα στοιχεία δεν έχουν ταξινομημένο δείκτη, επομένως η έννοια του "εισάγετε στο μέσο" δεν εφαρμόζεται άμεσα.

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

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

Επομένως, αν η δομή δεδομένων είναι ταξινομημένη και υλοποιείται ως πίνακας, η εισαγωγή στο μέσο είναι O(n). Αν είναι ένας πίνακας κατακερματισμού, η εισαγωγή είναι O(1), αλλά η έννοια του "μέσου" δεν εφαρμόζεται.