Что такое Big O notation

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

Умеете ли вы оценивать код до того, как он попадёт в браузер к пользователю со слабым телефоном. От фронтендера ждут не доказательств, а умения увидеть вложенный цикл в обработке списка и сказать, как вырастет время при росте данных.

Как отвечать

Big O описывает, как растёт число операций при росте размера входа, отбрасывая константы и младшие слагаемые. Это про поведение на больших входах, а не про миллисекунды: линейный алгоритм с тяжёлым телом бывает медленнее O(n log n) на реальных размерах.

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

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

Фронтенду полезно привязать к своим задачам: includes или find внутри map по тому же списку это скрытый квадрат, лечится Map или Set; сортировка и фильтрация на каждый рендер вместо мемоизации; отрисовка тысяч узлов вместо виртуализации; чтение геометрии элемента в цикле, где каждый шаг заставляет браузер пересчитывать раскладку.

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

Оценивают только свой цикл и не считают, что стоит вызов внутри. Сортировка внутри цикла или поиск по массиву превращают линейный на вид код в квадратичный.

Молчат про память. Копия массива на каждой итерации или накопление через объединение в reduce это частый ответ на вопрос, почему вкладка съела гигабайт.

Приводят нотацию как приговор: слышат про квадрат и переписывают код, где элементов десяток. Взрослый ответ включает оценку реального размера входа и замер, а не только букву.