Существует ли сложность алгоритмов по использованию памяти

Что проверяют

Вопрос звучит наивно, но это проверка на понимание асимптотики: назовёте ли вы пространственную сложность, отделите ли дополнительную память от памяти под сам вход и приведёте ли примеры, где время и память меняются местами. Для Go смотрят ещё и на то, знаете ли вы, чем измеряют аллокации на практике: асимптотика ничего не говорит про давление на сборщик мусора.

Как отвечать

Да, она есть и обозначается так же. Обычно имеют в виду дополнительную память, то есть всё сверх входных данных: без этой оговорки любой алгоритм, читающий массив, был бы O(n).

Приведите пары:

• поиск максимума, O(1): пара переменных независимо от длины;
• подсчёт частот через карту, O(n) по памяти ради линейного времени вместо O(n log n) с сортировкой;
• сортировка слиянием, O(n) на буфер; сортировка на месте, O(1) сверх входа, но обмены ломают стабильность;
• рекурсия: глубина стека тоже память, у быстрой сортировки это O(log n) при удачном выборе опорного элемента и O(n) при неудачном.

Про Go скажите практическую часть: go test -bench . -benchmem показывает B/op и allocs/op, побег переменной в кучу виден через go build -gcflags=-m, а make([]T, 0, n) заранее убирает цепочку перевыделений при append. Это и есть ответ на вопрос «как измеряется»: не в килобайтах на бумаге, а замером.

Где спотыкаются

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

Считают память только по явно созданным структурам. Стек рекурсии и промежуточные значения тоже расходуются, и именно на них падает обход глубокого дерева, где по коду вообще ничего не выделяется.

Уверенно говорят, что срез экономнее массива. Срез это заголовок с указателем на тот же массив, а рост через append копирует данные и оставляет старый блок сборщику. Выигрыш появляется от передачи без копирования, а не от самой динамичности.