このアルゴリズム解析は正しいですか

私はアルゴリズム設計マニュアルを読んでいますが、この解決策はマニュアルにはありません。私はそれが正しいかどうか疑問に思っていたので、それを考え出して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

$\sum_{i=1}^{n}\sum_{j=i+1}^{n}\sum_{k=i+j-1}^{n}1$

我々は最初の合計を解決するため、我々は

$\sum_{i=1}^{n}\sum_{j=i+1}^{n}(n - i - j + 1)$

$\sum_{i=1}^{n}(n^2 - 5n - 2 - i^2 - 3i)$

を取得し、最終的な方程式は次のようになります。

$n^3 - 5n^2 - 2n - \frac{n(n+1)(2n+1)}{6} - \frac{3n(n+1)}{2}$

は、n^4が負であることを考えると、私たちは、このアルゴリズムの実行している時間が $\Theta (n^3)$

で、それが正しいことを結論づけることができますか？

最終結果は正しいです。詳細計算には少なくとも1つのエラーがあります。aからbまでの合計はb-a + 1です。

また、次の用語の記号は無関係です（あなたはn^2を意味すると仮定します）。 n^2項が正であっても、ランタイムはTheta（n^3）になります。

2016-11-19 19:12:19 Henry

私は2n^2の2nを間違えたので、これがn^4を得た理由です。合計のことについては、エラーを指摘することはできますか？ – SuburbanFilth

私はそれをやったと思った：aからbへの境界で1を合計すると、結果はb-a + 1であり、b-aではない。 – Henry

mbもう一度、私は文を正しく読まなかった – SuburbanFilth

答えて