Сколько дополнительной памяти требует решение со словарём, не считая возвращаемых данных?

Использование словаря (хэш-таблицы) требует дополнительной памяти, пропорциональной количеству уникальных ключей, которые в него добавляются. Если у вас есть N уникальных элементов, то память будет примерно O(N), так как для каждого ключа и связанного с ним значения выделяется место.

Например, если вы создаёте словарь для подсчёта количества вхождений слов в тексте, то память будет расти с увеличением количества уникальных слов. При этом сама структура словаря обычно содержит дополнительные накладные расходы на хранение хэш-значений и управление коллизиями, но в целом оценка O(N) по дополнительной памяти — наиболее практичная.