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

Question

Я использую этот алгоритм в своей программе:

for( i=0 ; i<N ; i++ )

  for( j=i+1 ; j<N+1 ; j++ )

     for( k=0 ; k<i ; k++ )

          doWork();

Может кто-нибудь помочь мне найти временную сложность этого фрагмента?Я думаю, что для первых двух циклов это

N*(N+1)/2 

верно?а как насчет трех петель все вместе?

Answer 1

Спасибо @Tim Meyer, чтобы исправить меня:

Простое уравнение дает для (N = 0,1,2,3,4,5,6, 7, 8 ...) следующие серии: 0, 0, 1, 4, 10, 20, 35, 56, 84 ..., что разрешается следующей формулой:

u(n) = (n - 1)n(n + 1)/6 

Таким образом, оно будет иметь O ((N - 1)N (N + 1) / 6) сложность времени, которую можно упростить до O (N ^ 3)

Answer 2

Формально вы можете сделать следующее: