Что такое Bi gO этой функции

Question

Концепция обозначения Big-O не нова для меня, но я только что видел этот фрагмент кода, где автор говорит, что это кубическое c время или O(N^3), и я запутался, я бы сказал, что это O(n^2), кто-нибудь может мне помочь в правильном направлении?

Спасибо!

long sum = 0;
for( int i = 0; i < n; i++ ) {
  for( int j = 0; j < n*n; j++ ) {
    sum += i - j;   
  }
}

Answer 1

Если мы предположим, что вычитание двух целых чисел может быть выполнено в постоянное время (а также увеличение целых чисел и т. Д. c.), Это будет O (n ³ ) .

Во внутреннем for l oop счетчик j проходит от j = 0 до j = n*n. Так что это означает, что каждый раз, когда мы запускаем внутренний for l oop, он будет выполнять n*n итераций.

Мы делаем это n раз, поскольку внешние циклы for запускаются из i = 0 до i = n. Таким образом, общее количество итераций составляет n*n*n, и, таким образом, O (n ³ ) .