Kolik dodatečné paměti vyžaduje řešení se slovníkem, nepočítaje vrácená data?

Použití slovníku (hash tabulky) vyžaduje dodatečnou paměť, která je úměrná počtu unikátních klíčů, které do něj přidáváte. Pokud máte N unikátních prvků, bude paměť přibližně O(N), protože pro každý klíč a s ním spojenou hodnotu je vyhrazeno místo.

Například pokud vytváříte slovník pro počítání výskytu slov v textu, paměť poroste s nárůstem počtu unikátních slov. Struktura slovníku obvykle obsahuje dodatečné náklady na uložení hash hodnot a správu kolizí, ale obecně je odhad O(N) na dodatečnou paměť nejpraktičtější.