Here's the code:

for (int i = 0; i < n; i  ) {
    for (int j = 0; j < n * n; j  ) {
        for (int k = 0; k < j; k  ) {
            sum  ;
        }
    }
}

I need to evaluate the Time complexity in Big-O notation of the nested loops above.

Is it just O(n) * O(n) * O(n) O(1) to make O(n^3)? Or is there more to it?

CodePudding user response：

The most inner loop is executed in quadratic time (not constant), hence it should be O(n) * O(n^2) * O(n^2) = O(n^5).

Here are all the costs:

• Most outer loop - O(n)

• The second loop - O(n^2) for each element for the outer loop

• The most inner loop - O(n^2) for each element for the second loop

CodePudding user response：

for (int i = 0; i < n; i  ) -> runs n times.
 for (int j = 0; j < n * n; j  ) -> runs n² times.
  for (int k = 0; k < j; k  ) -> runs n² times (k == j == n²)

n * n² * n² = n^5.

sum is an operation of constant runtime (1) and can therefore be ignored.

CodePudding user response：

The second loop isn't O(n), it's O(n^2) by itself.