Время — O(n²), дополнительная память — O(1), если compare ничего не накапливает. Число сравнений равно n(n−1)/2.
Как оценить сложность цикла с вложенным проходом
Время — O(n²), дополнительная память — O(1), если compare ничего не накапливает. Число сравнений равно n(n−1)/2.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Для массива длины n выполняется for(let i=0;i<n;i++) for(let j=i+1;j<n;j++) compare(a[i],a[j]). compare занимает O(1). Оцените время и дополнительную память.
Ответ
Время — O(n²), дополнительная память — O(1), если compare ничего не накапливает. Число сравнений равно n(n−1)/2.
Внешняя итерация i выполняет n−i−1 сравнений; сумма даёт треугольное число, а не n² буквально. В асимптотике постоянный коэффициент и линейное слагаемое отбрасываются. Если сохранять все найденные пары, память результата может вырасти до O(n²): её нужно оценивать отдельно от памяти самого обхода.