Ile dodatkowej pamięci wymaga rozwiązanie z słownikiem, nie licząc danych zwracanych?

Użycie słownika (tablicy haszującej) wymaga dodatkowej pamięci proporcjonalnej do liczby unikalnych kluczy, które są do niego dodawane. Jeśli masz N unikalnych elementów, pamięć będzie w przybliżeniu O(N), ponieważ dla każdego klucza i powiązanej z nim wartości przydzielane jest miejsce.

Na przykład, jeśli tworzysz słownik do liczenia liczby wystąpień słów w tekście, pamięć będzie rosła wraz z rosnącą liczbą unikalnych słów. Struktura słownika zazwyczaj zawiera dodatkowe narzuty na przechowywanie wartości hash i zarządzanie kolizjami, ale ogólnie szacunkowe O(N) w dodatkowej pamięci jest najbardziej praktyczne.