Что означает сложность алгоритма O(n^2)

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

Умеете ли вы оценивать код по асимптотике и замечать квадрат там, где вложенных циклов на первый взгляд нет. Для Go это чаще не учебная сортировка, а работа со строками, срезами и линейным поиском внутри цикла.

Как отвечать

Сложность O(n^2) означает, что время растёт как квадрат размера входа: вход вдвое больше, работы вчетверо. Запись асимптотическая, константы и младшие слагаемые в ней отброшены, поэтому она говорит про рост, а не про абсолютную скорость.

Откуда квадрат берётся на практике:

• вложенные циклы по одному набору: поиск пары, сравнение всех со всеми, пузырьковая сортировка и сортировка выбором;
• склейка строк в цикле через s += x: строка неизменяема, каждая итерация копирует всё накопленное, лечится strings.Builder;
• линейный поиск внутри цикла: проход по второму срезу для каждого элемента первого. Замена на map[string]struct{} даёт линейное время;
• удаление элементов по одному через append(s[:i], s[i+1:]...) в цикле: каждый вызов сдвигает хвост.

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

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

Считают вложенность отступов вместо операций. Два цикла, где внутренний идёт по константе, дают линейное время, а один цикл с strings.Contains или slices.Index внутри уже квадратичен.

Путают средний случай и худший. Быстрая сортировка в среднем работает за O(n log n), но рукописный вариант с крайним опорным элементом на почти отсортированных данных скатывается в квадрат. Стандартная сортировка в Go от такого входа защищена.

Останавливаются на букве O и не проверяют гипотезу. Асимптотика ничего не говорит про константы и аллокации, поэтому вывод о том, что стало быстрее, делается по go test -bench и профилю, а не по формуле.