这是算法分析是正确的

Question

我读的算法设计手册和这个解决方案是不说明书中无。我花了30分钟计算出来，所以我想知道它是否正确。下面是该函数的伪代码：

function conundrum(n) 
    r:=0 
    for i:=1 to n do 
    for j:=i+1 to n do 
     for k:=i+j−1 to n do 
     r:=r+1 

我们解决第一个求和，我们得到

最终的公式应该是：

鉴于第n^4负，我们可以得出结论，该算法的运行时间为

它是正确的吗？

Answer 1

最终结果是正确的，详细计算中至少有一个错误：从a到b在1之上的和是b-a + 1。

此外，下一个词的符号是不相关的（我假设你的意思是n^2）。即使n^2项是正数，运行时也是Theta（n^3）。