асимптотический анализ трех вложенных циклов для

Question

Я хочу, чтобы вычислить тэта сложность этого вложенная цикл:

for (int i = 0; i < n; i++) { 
     for (int j = 0; j < i; j++) { 
      for (int k = 0; k < j; k++) { 
       // statement 

Я бы сказал, что п^3, но я не думаю, что это правильно, потому что каждый для цикла не идет от 1 до n. Я сделал несколько тестов:

п = 5 -> 10

10 -> 120

30 -> 4060

50 -> 19600

Так должно быть между п^2 и n^3. Я пробовал формулу суммирования и так, но мои результаты слишком высоки. Хотя n^2 log (n), но это также неправильно ...

Answer 1

Это O(N^3). Точная формула (N*(N+1)*(N+2))/6

Answer 2

Использование Sigma нотации является эффективным шаг за шагом методологии: