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

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

Για παράδειγμα, αν δημιουργείτε ένα λεξικό για να μετρήσετε τον αριθμό των εμφανίσεων των λέξεων σε ένα κείμενο, η μνήμη θα αυξάνεται με την αύξηση του αριθμού των μοναδικών λέξεων. Επιπλέον, η δομή του λεξικού συνήθως περιλαμβάνει επιπλέον έξοδα για την αποθήκευση των τιμών hash και τη διαχείριση των συγκρούσεων, αλλά γενικά η εκτίμηση O(N) στη πρόσθετη μνήμη είναι η πιο πρακτική.