Analyze Triple Loop - j and k start with i^2 and j^2 respectively

Question

for (int i = 1 to n) {

  for (int j = i*i to n) {

    for (int k = j*j to n) {

      sum += a[i]*b[j]*c[k]

    }

  }

}

Answer 1

For the innermost loop to execute, the condition j² ≤ n must hold, meaning j ≤ n^0.5.

In the middle loop, j ranges from i² to n. Since j ≤ n^0.5, the range for j is from i² to n^0.5. For the middle loop to run, the condition i² ≤ n^0.5 must be satisfied, which implies i ≤ n^0.25.

Therefore, the outer loop runs from i = 1 to i = n^0.25.

Thus, the total time complexity is n^0.25⋅n^0.5⋅n = O(n^1.75) or O(n^7/4).