CODEWITHSUNDEEP
timecomplexity-theory
luka lazarevic
luka lazarevic

Reputation: 21

How do I calculate the time complexity of this algorithm?

I have been trying to calculate the time complexity of this algorithm but I don't think that I am right.

Since it can't be n^2, I came up with a formula that goes O(n*(j*(1+j)*50), but I am still not sure enough.

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i ; j++)
        for (int k = 1; k <= 100; k++)
           cout << "Hello";

Any help would be appreciated.

Upvotes: 1

Views: 70

Answers (1)

giusti
giusti

Reputation: 3538

This is O(n²) indeed. The inner loop runs in constant time. It is the same as

for(int i = 1;i<=n;i++)
  for(int j = 1;j<=i;j++) {
      cout << "Hello";
      cout << "Hello";
      cout << "Hello";
      cout << "Hello";
      /* repeats 96 mores times */
  }

More specifically, you can calculate the number of steps as

T(n) = 1 + 2 + 3 + ... + n
     = n * n(1 + n)/2
     = (n² + n)/2

Constants don't matter, so this function grows in O(n² + n) which is simply O(n²).

Instead of unrolling the inner loop, you could multiply everything by 100, but this wouldn't change the complexity.

Upvotes: 2

Related Questions