Câtă memorie suplimentară necesită o soluție cu dicționar, fără a include datele returnate?

Utilizarea unui dicționar (tabel hash) necesită memorie suplimentară proporțională cu numărul de chei unice care sunt adăugate. Dacă aveți N elemente unice, memoria va fi aproximativ O(N), deoarece pentru fiecare cheie și valoarea asociată se alocă spațiu.

De exemplu, dacă creați un dicționar pentru a număra de câte ori apar cuvintele într-un text, memoria va crește odată cu creșterea numărului de cuvinte unice. În plus, structura dicționarului include de obicei costuri suplimentare pentru stocarea valorilor hash și gestionarea coliziunilor, dar în general, estimarea O(N) pentru memoria suplimentară este cea mai practică.