Каково время выполнения этого вложенного цикла for?

Question

for i = 1 to n   
  for j = 1 to i - 1

Является ли время выполнения этого O (n ^ 2)? Есть ли хороший способ визуализировать вещи при подходе к этим типам проблем, чтобы найти правильный ответ?

Answer 1

Внутренний цикл выполняется

1 + 2 + 3 + 4 + 5 +...n-1 = n*(n-1)/2 times

с использованием формулы для суммы арифметической прогрессии, поэтому общая сложность равна O (n ^ 2)

Answer 2

Каждый для цикла равен O (n), два для цикла O (n) * O (n) = O (n ^ 2)

Проверьте эту ссылку out. Автор объясняет хорошие подходы к определению времени выполнения.