Два вложенных цикла не обязательно выполняют ровно n² действий. Здесь рассматриваются только пары разных элементов, причём каждая один раз:
n = 5
pairs = 0
for i in range(n):
for j in range(i + 1, n):
pairs += 1
print(pairs) # 10
Число пар — n(n − 1)/2. При росте n главным становится квадрат, поэтому затраты растут как Θ(n²). Удаление половины сравнений улучшает время, но не меняет этот класс роста.
Разбор Big O объясняет, что такая оценка не обещает конкретное число миллисекунд. На маленьких данных влияют константы и реализация; для реального времени нужен замер.
Всегда уточняйте, что оцениваете: худший случай, средний, время или дополнительную память. Одно O(n) без контекста легко понять неправильно.