algorithm - 算法运行时间T(n)

Question

我已经分析了以下算法的运行时间是分析theta但它的运行时间可能是Big O吗？

                               Cost             Time
1.  for i ←1 to n                c1             n   
2.      do for j ← i to n        c2             n
3.          do k ← k+ j          c3             n-1
T(n) = c1n +c2n+c3(n-1)
     = C1n+C2n+C3(n-1)
     = n(C1+C2)+n-1
     = n+n-1
Or T(n) = Ө(n)
So running time is Ө(n)

Answer 1

您的循环将按如下方式继续(众所周知的算术 progression 公式):

-也可以估计为因为 big-O 给出了多数估计。