C++ - Big-O Notation

Question

For some reason im unable to solve this. what will be the Big-o Notation

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
        c[i][j] = 0;
        for (int k = 0; k < n; k++)
            c[i][j] += a[i][k] * b[k][j];
    }

Answer 1

for (int i = 0; i < n; i++)
 for (int j = 0; j < n; j++) {
  c[i][j] = 0;
  for (int k = 0; k < n; k++) c[i][j] += a[i][k] * b[k][j];
 }

It looks like it's O(n^3) because it has 3-level loops.

Answer 2

The answer is: O(n^3)

Because the outer most loop executes N times.
For each element in that loop the middle loop executes N times.
For each element in the middle loop, the inner most loop executes N times.

Total looping is N*N*N = N^3

This statement executes N^2 times c[i][j] = 0; but it is irrelevant compared to the inner most statement which executes N^3 times.

Answer 3

The way to work this out is to calculate the number of operations in terms of n, and then discard less-significant terms (if there are any)...

Answer 4

Steven, if we simply tell you what the complexity is, you're not going to learn how to compute the complexity. Please suggest what you think the complexity is and why. Then we can better help you.