這是算法分析是正確的

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）。