Какова временная сложность следующего l oop?

Question

Я не могу найти ответ для этого онлайн (Обратите внимание, что внутренний l oop до i - не n:

for(int i = 1; i < n; i++) {
   for(int j = 1; j < i; j++) {
     printf("foo")
   }
 }

Для значений i = 1,2,3. .., оператор будет напечатан 0, 1, 2 .. раз, поэтому их суммирование приведет к O (n ^ 2). Я прав?

Answer 1

Временная сложность кода будет O(n^2).

Внешний l oop имеет временную сложность O(n), а внутренний l oop начинается с 0 to i.

Следовательно, сложность времени будет O(n^2)

Answer 2

Вы в основном выполняете это количество операций:

1 + ... + (n - 2) = 
(n - 2 + 1) * (n - 2) / 2 =
(n - 1) * (n - 2) / 2 =
(n² - 3n - 2) / 2

Следовательно

O((n² - 3n - 2) / 2) = 
O(n² - 3n - 2) = 
O(n²)