Quanta memoria aggiuntiva richiede una soluzione con dizionario, escludendo i dati restituiti?

L'uso di un dizionario (tabella hash) richiede memoria aggiuntiva proporzionale al numero di chiavi uniche che vengono aggiunte. Se hai N elementi unici, la memoria sarà circa O(N), poiché viene allocato spazio per ogni chiave e il valore associato.

Ad esempio, se crei un dizionario per contare il numero di occorrenze delle parole in un testo, la memoria crescerà con l'aumentare del numero di parole uniche. La struttura del dizionario di solito include costi aggiuntivi per la memorizzazione dei valori hash e la gestione delle collisioni, ma in generale, la stima di O(N) in memoria aggiuntiva è la più pratica.