数据结构（C语言）的时间复杂度

Question

想问一下这个时间复杂度咋解释，为啥不是ijn直接相乘，而是求和∑，弄不明白

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