Объяснение
Сложность описывает рост числа операций, а не секунды. Два вложенных цикла по n элементам дают n² итераций; удвоение n увеличивает работу примерно вчетверо. Инвариант — утверждение, истинное до и после каждого шага алгоритма.
Задача для самостоятельного решения
Посчитайте сравнения полного попарного перебора для n=10 и n=20.
Показать разбор ответа
Если перебираются все упорядоченные пары, получаем 100 и 400. Если только пары i<j, получаем n(n−1)/2: 45 и 190. Сначала уточняйте границы циклов.