Strewen
Если честно то не знаю что та кое О(n**2). Можете рассказать? А так я только вчера начал изучение. Пытаюсь сделать хоть что то)
Если есть n элементов, то сколько (теоретически) шагов сделает алгоритм (проще понять на примере поиска максимума и сортирующих, но вообще это просто способ оценки алгоритма)
О(n) значит сколько элементов столько и шагов (например искали максимальный),
O(n**2) - это варианты попарного перебора элементов(каждый сравнили с каждым, примерно как у Вас)
O(nlogn) - обычно получается когда алгоритмы похитрее, задача как бы разбивается на подзадачи (группа алгоритмов divide and conquer часто такая), например, merge sort - сортировка по 1 по 2 по 4 по 8 итд (отсюда логарифм в формуле)
Ну и сразу подводный камень - есть к примеру quicksort, он O(n**2), но если последовательности не специально такие чтобы он работал медленно (killer sequences) то он многие O(nlogn) уделывает