時間の複雑さ3つのforループ

Question

私は、このアロギームの時間複雑さはn^3だと言われましたが、最初のループはn回反復され、2回目の反復はn^2、最後は1回繰り返されます。 n(n-1)/2 + nが最初にn回実行されるため、n-1、次にn-3.....1となるため、時間の複雑さはn^2になるはずです。誰かがこれが間違っている理由を伝えることができますか？

procedure alg 1(int n) 
t := 0 
for i := 1 to n do 
    for j := 1 to n do 
     for k := n to j do 
      t := i ∗ j ∗ k 

Answer 1

n(n-1)/2 + n = (n^2-n)/2 + nから、その最後のループはまだBig-Oh（n）です。 3つのネストされたループがn^2で終わる可能性がある唯一の方法は、最後のものがO（1）だった場合です。

ちょうどビッグああ、最後のループのためにどのように変化するかを想像：

n = 1 | (n^2-n)/2 + n = 1 
n = 10 | (n^2-n)/2 + n = 55 
n = 100| (n^2-n)/2 + n = 5050 

これは、第3のループでまともな定数を持っていますが、それはまだ指数によって支配されます。