Как оценить сложность по памяти в терминах Big O, если объем памяти не зависит от длины массива

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

Понимаете ли вы, что входит в пространственную сложность, и отличаете ли O(1) на словах от O(1) в реальном коде на Kotlin. Следом обычно спрашивают, остаётся ли O(1) у рекурсивного решения и сколько памяти съедает цепочка map и filter.

Как отвечать

Если объём дополнительной памяти не растёт с длиной массива, это O(1). Константа может быть и заметной: массив из 26 счётчиков для латинских букв тоже O(1), потому что алфавит фиксирован и от n не зависит. Сам входной массив обычно не учитывают, речь о вспомогательной памяти (auxiliary space); стоит так и сказать, чтобы не было путаницы.

Типичные решения с O(1):

• два указателя: разворот массива на месте, поиск пары с заданной суммой в отсортированном массиве;
• накопители: максимум, сумма, счётчик за один проход;
• изменение на месте: reverse() у IntArray или MutableList меняет исходные данные и копию не создаёт.

Дальше покажите, где O(1) незаметно ломается в Kotlin:

• копирующие функции: reversed(), sorted(), map, filter возвращают новую коллекцию, это уже O(n). У asSequence() промежуточных списков нет, но итоговый toList() всё равно O(n);
• рекурсия: каждый вызов занимает кадр стека, рекурсивный проход по массиву глубиной n стоит O(n). Модификатор tailrec компилирует хвостовую рекурсию в цикл и возвращает O(1);
• упаковка: List<Int> хранит объекты Integer, а IntArray примитивы. На асимптотику это не влияет, но на Android при больших данных разница в памяти и нагрузке на сборщик мусора заметна.

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

Называют O(1), потому что «новых массивов нет», и не считают стек рекурсии. На большом входе такой код падает со StackOverflowError задолго до того, как кончится куча.

Считают любую аллокацию в цикле ростом памяти. Если объект на каждой итерации создаётся и сразу становится мусором, пиковый объём не растёт, и оценка остаётся O(1). Асимптотика про пиковый объём, а не про число аллокаций.

Думают, что O(1) значит «мало». Буфер фиксированного размера в несколько мегабайт тоже O(1), и на слабом устройстве он важнее формальной оценки.