big-o - 次のコードの時間計算量 (big-O 表記) は?

Question

次のコードの時間の複雑さは何だろうと思っていました。

私の意見では、以下のコードの時間計算量 (Big O) は O(n^4) になります。

皆さんはどう思いますか？

int result = 0;
for(int i =1; i<n*n; i++){
  for (int j=i; j*j <n; j++){
    for(int k =j; k*k <n; k++){
      result++;
     }
  }
}

Answer 1

私には次のように見えn^(2.75)ます：

- outer loop: n^2
- first inner loop is sqrt(n)
- second inner loop is sqrt(sqrt(n))

の合計：

n^2 * sqrt(n) *  sqrt(sqrt(n)) = n^(2+ 0.5 + 0.25) = n^(2.75)

Answer 2

シグマ記法を使用した正式な手順 (検証が必要) では、次のようになります。