一个时间复杂度的问题

Question

为什么圆圈3那里得到O（1/6 n^3）呢？满足1<=k<=j<=i<=n的所有(i,j,k)有多少组，为什么三个变量一共有6种可能的大小关系呢？

Answer 1

当i=1时，内层for循环执行次数是1=1
当i=2时，内层for循环执行次数是1 + （1+2）=4
当i=3时，内层for循环执行测试是 1+（1+2）+（1+2+3）=10
当i=4时，内层for循环执行测试是 1+（1+2）+（1+2+3）+（1+2+3+4）=20
...
当i=n时，内层for循环执行测试是 1+（1+2）+（1+2+3）+（1+2+3+4）+ ...+(1+2+..+n)
相当于a(n)=a(n-1)+n(n+1)/2，这个数列最后a(n)的表达式为：
a(n)=n(n+1)(n+2)/6
时间复杂度取幂次最高的项就是 1/6n^3