Какая алгоритмическая сложность функции с двумя вложенными циклами по массивам

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

Заметите ли вы, что при разных массивах это не квадрат, и посмотрите ли внутрь тела цикла.

Как отвечать

Ответ зависит от того, по каким массивам идут циклы.

Один и тот же массив длины n: получается n умножить на n, то есть O(n²).

Разные массивы длин n и m: O(n · m), и это не то же самое, что квадрат. Если один массив короткий и его длина ограничена константой, сложность фактически линейная. Называть здесь O(n²) неверно.

Внутренний цикл зависит от внешнего (for j = i + 1): сумма даёт примерно n²/2 операций, а константы отбрасываются, значит всё равно O(n²).

Дальше главное: посмотреть, что внутри тела. Сложность цикла это число итераций, умноженное на стоимость итерации. Классическая ловушка выглядит так:

for (const a of listA) {
  if (listB.includes(a)) result.push(a);   // includes это O(m)
}

Здесь цикл один, а сложность O(n · m), потому что поиск внутри линейный. То же самое дают indexOf, find, filter и конкатенация строк внутри цикла.

И сразу назовите оптимизацию, её обычно и ждут:

const setB = new Set(listB);              // O(m)
const result = listA.filter((a) => setB.has(a));   // O(n)

Стало O(n + m) ценой дополнительной памяти под множество. Это самый частый способ убрать квадрат из реального кода.

Полезное дополнение про практику: асимптотика описывает поведение при росте. На двух массивах по сто элементов вложенный цикл отработает быстрее, чем построение множества. Разница появляется на тысячах и становится критичной на десятках тысяч.

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

Называют O(n²) для циклов по разным массивам.

Не учитывают стоимость операций внутри тела цикла.

Считают, что filter и includes бесплатны, раз это встроенные методы.

Оптимизируют вложенный цикл на данных, где он и так мгновенный.