Как определить сложность метода

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

Умеете ли вы оценить метод по коду, а не перечислить O(1), O(n) и O(n²) по памяти. Следом обычно дают конкретную функцию на JavaScript и просят найти, где в ней спрятана квадратичная сложность.

Как отвечать

Покажите порядок рассуждения:

• что такое n: назовите, от чего растёт стоимость. У метода может быть два входа, и тогда честный ответ O(n · m), а не O(n²);
• циклы: последовательные складываются, вложенные по тем же данным перемножаются. Константы и младшие слагаемые отбрасываются: O(2n + 10) это O(n);
• встроенные методы: includes, indexOf, find, splice и shift проходят массив, то есть это O(n). Вызванные внутри цикла, они дают O(n²). Set.has и Map.get в среднем O(1), sort это O(n log n), в V8 под ним TimSort;
• рекурсия: считайте число вызовов и работу в каждом. Наивный Фибоначчи даёт O(2ⁿ), бинарный поиск O(log n), сортировка слиянием O(n log n);
• память: дополнительные массивы, объекты и глубина стека рекурсии тоже входят в оценку;
• амортизация: push в среднем O(1), хотя изредка массив перевыделяет хранилище.

Привяжите ответ к Node.js. JavaScript выполняется в одном потоке, поэтому квадратичный алгоритм на 100 тысячах элементов блокирует event loop, и ждут все запросы процесса, а не один. Проверить оценку на практике помогают performance.now(), профиль через node --cpu-prof и monitorEventLoopDelay из perf_hooks.

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

Не замечают скрытых циклов. Классика: reduce со спредом { ...acc, [key]: value } на каждой итерации копирует весь накопленный объект, и линейный на вид код становится O(n²).

Путают асинхронность со сложностью. await в цикле против Promise.all меняет задержку, но не объём работы, и асимптотика у обоих вариантов одна.

Считают Big O точным временем. Нотация говорит о росте, и на маленьких n линейный поиск по массиву из десяти элементов бывает быстрее хэш-таблицы.