Kiek papildomos atminties reikalauja žodynu pagrįstas sprendimas, neįskaitant grąžinamų duomenų?

Žodyno (hash lentelės) naudojimas reikalauja papildomos atminties, proporcingos unikalių raktų skaičiui, kurie į jį yra pridedami. Jei turite N unikalių elementų, atmintis bus maždaug O(N), nes kiekvienam raktui ir su juo susietai vertei skiriama vieta.

Pavyzdžiui, jei kuriate žodyną, kad suskaičiuotumėte žodžių pasikartojimų skaičių tekste, atmintis didės su unikalių žodžių skaičiaus didėjimu. Be to, žodyno struktūra paprastai apima papildomas išlaidas hash reikšmių saugojimui ir kolizijų valdymui, tačiau apskritai, O(N) įvertinimas papildomai atminčiai yra pats praktiškiausias.