CODEWITHSUNDEEP
c++big-o
Steven
Steven

Reputation: 53

C++ - Big-O Notation

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];
    }

Upvotes: 2

Views: 1752

Answers (4)

Jon Purdy
Jon Purdy

Reputation: 54971

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

Or O(n · n · (1 + n · 1)) which is equivalent to O(n · n · n) or O(n3) after collapsing the constant operations.

Upvotes: 4

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272467

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)...

Upvotes: 0

Brian R. Bondy
Brian R. Bondy

Reputation: 347216

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.

Upvotes: 2

Ming-Tang
Ming-Tang

Reputation: 17651

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.

Upvotes: 2

Related Questions