Сложность во время выполнения вложенного цикла for, но внутренний идет только до текущего индекса внешнего

Question

for i in range(n):
   for j in range(i):
      print j

Несмотря на то, что внутренний цикл идет только до длины текущего индекса внешнего цикла, могу ли я утверждать, что это O (n ^ 2)?

Answer 1

Цикл, считающий до n, описывает линию, вложенный цикл, считающий до n, описывает квадрат.

Когда внутренний цикл поднимается до индекса внешнего цикла, вы покрываете половину квадрата в форме треугольника:

+----+
|.   |
|..  |
|... |
|....|
+----+

, чтобы вы могли более точно предсказать время выполнения, рассчитав площадь треугольника. Но нотация Big-O заключается не в том, чтобы получить точное время выполнения, а в том, чтобы сравнить, как масштабируется время выполнения при добавлении дополнительных данных. Вы хотите знать, к какой из этих строк ваша программа будет ближе всего. Размер треугольника все еще увеличивается пропорционально n*n. Покрытие на половине квадрата недостаточно для того, чтобы сдвинуть программу ближе к другому классу сложности.