Как алфавит влияет на сложность подсчёта частот

Условие

Текст длины n состоит из символов алфавита размера m. Алгоритм обнуляет массив из m счётчиков, проходит текст и затем выводит все m частот. Оцените сложность.

Ответ

Время O(n+m), дополнительная память O(m). Инициализация и обход всего алфавита учитываются отдельно от прохода по тексту.

Если алфавит фиксирован малой константой, оценку по n часто сокращают до O(n). Если m тоже входной параметр, так делать нельзя. Словарь только встреченных символов может уменьшить память до O(min(n,m)), но имеет другие константы и зависит от реализации хеширования.