Какова временная сложность этого вложенного цикла?

Question

Я наткнулся на цикл, для которого я не уверен, какова сложность времени.Это следующий цикл:

for(i = 1; i <= n^2; i++){
   for(j = 1; j <= i; j++) {
      //some elementary operation
   }
}

Я бы сказал, что внешний цикл for выполняется в n ^ 2, а внутренний цикл for также будет выполняться в n ^ 2, как для каждой итерации внешнего цикла.цикл мы делаем п ^ 2 - (п ^ 2 - 1), п ^ 2 - (п ^ 2 - 2), ..., п ^ 2.Я полностью иду в неправильном направлении здесь?

Таким образом, сложность времени будет в п ^ 4

Answer 1

Число операций будет:

1 + 2 + 3 + 4 + 5 + ... + n²

Что равно (n² * (n² - 1)) / 2.

Обозначение большого O - O (n ^4).Вы правы.

Answer 2

Здесь происходит простая арифметическая прогрессия.

Каждая новая итерация увеличивается на 1.

Внешний цикл будет выполнять n ^ 2 операций, что приведет к следующей последовательности:

1 + 2 + 3 + ... + n + ... + n^2 = n^2 (n^2+1) / 2 = O(n^4)