CODEWITHSUNDEEP
c++algorithmtime-complexity
H Creptef
H Creptef

Reputation: 11

Complexity of an specific algorithm with 3 for?

I have a question if you can tell me if i do it right! We have this algorithm

for(i=0;i<n*n;i++){
  for(j=i;j<n;j++)
     for(k=0;j<=9;k++)
              c+=2;

I want to find complexity of this if you can tell me if i doing right

sum 0,n*n (sum i,n(20))= sum 0,n*n ((n-i+1)*20) = sum 0,n*n (n) - sum 0,n*n (i) + n*n*20
=nn20 + (nn-0+1)(n) -sum 0,n*n (i)
=n*n*n+nn20 -sum 0,n*n (i)

so O(n*n*n)

Is this right ?

Upvotes: 0

Views: 107

Answers (2)

Thomas Sablik
Thomas Sablik

Reputation: 16447

The statement 

c+=2;

is called exactly

10 (n + n-1 + n-2 + ... + 1) = 5n² + 5n = 10 * sum i=1,n (i)

times. This is O(n²). The loop

for(int i = 0; i < n*n; i++)

iterates n*n times but if i >= n it does nothing. So effectively the outer loop iterates n * (n-1) times with constant complexity (O(1), it does nothing).

The loop 

for(int j = i; j < n; j++)

iterates n - i times. And the loop

for(int k=0; k <= 9;k++)

iterates 10 times.

This is 

10 (n + n-1 + n-2 + ... + 1) = 5n² + 5n = 10 * sum i=1,n (i)

With this code you can confirm the number of calls to c += 2:

#include <iostream>

int main() {
    for (int n = 1; n < 10; ++n) {
        int c = 0;
        for(int i = 0; i < n*n; i++)
            for(int j = i; j < n; j++)
                for(int k=0; k <= 9;k++)
                    c+=2;
        std::cout << c / 2 << " == " << "5*" << n << "*" << n << " + 5*" << n << " : " << std::boolalpha << (c / 2 == 5*n*n + 5*n) << '\n';
    }
}

Result:

10 == 5*1*1 + 5*1 : true
30 == 5*2*2 + 5*2 : true
60 == 5*3*3 + 5*3 : true
100 == 5*4*4 + 5*4 : true
150 == 5*5*5 + 5*5 : true
210 == 5*6*6 + 5*6 : true
280 == 5*7*7 + 5*7 : true
360 == 5*8*8 + 5*8 : true
450 == 5*9*9 + 5*9 : true

Upvotes: 1

Jarod42
Jarod42

Reputation: 217850

Complexity of:

for(i=0;i<n*n;i++)
  for(j=i;j<n;j++)
     for(k=0;k<=9;k++)
              c+=2;

Start with inner loop:

for(k=0;k<=9;k++) -> 10, so constant: O(1).

for(i=0;i<n*n;i++) would be O(n²), but the tricky

for(j=i;j<n;j++) discards any value i >= n.

so it becomes

for(i=0;i<n;i++)
  for(j=i;j<n;j++)
     for(k=0;k<=9;k++)
              c+=2;
for(i=n;i<n*n;i++) {}

Last loop for(i=n;i<n*n;i++) is O(n²) (but as no-op could be discarded by compiler)

  • for(i=0;i<n;i++) is O(n)
  • for(j=i;j<n;j++) is O(n) (as O(n/2) is O(n))

So final result is O(n²) + O(n²) so O(n²).

Upvotes: 2

Related Questions