CODEWITHSUNDEEP
algorithmbig-o
user697911
user697911

Reputation: 10581

Is this algorithm in N^2?

int sum = 0;
for (int i = 1; i <= N; i++)
    for (int j = 1; j <= i*i; j++)
        sum++;

Is this complexity 1 + 2^2 + 3^2 + 4^2 ... + N^2? How to represent it in big-o notation?

Upvotes: 2

Views: 110

Answers (4)

cppprog
cppprog

Reputation: 794

Another way to look at it is to use the "worst case" analysis. Originally, we have:

  • The outer for loop will run N times
  • The inner for loop will run i*i times

This might be confusing since i seems to be changing based on the outer for loop. However, in the "worst case" scenario, the largest value that i ever attains is N.

Therefore, just substitute N instead of i in our analysis. Now we have:

  • The outer for loop will run N times
  • The inner for loop will run N*N times

And the time complexity of this situation is of course O(N³).

Upvotes: 1

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

Straightforwardly, using Sigma notation:

enter image description here

Upvotes: 1

epipav
epipav

Reputation: 339

you can always use the intuitive way.

  • for i = 2 second loop 1 time, first loop 1 time. 1*1
  • for i = 3 second loop 9 times, first loop 2 times. 9*2
  • for i = 4 second loop 16 times, first loop 3 times 16*3
  • for i = 5 second loop 25 times, first loop 4 times. 25*4

. . .

you can see the pattern easily. it is (nˆ2)*(n-1) therefore its big o should be O(nˆ3)

Upvotes: -1

Mihai Maruseac
Mihai Maruseac

Reputation: 21460

The sum is N(N+1)(2N+1)/6 so your algorithm is O(N^3).

If you expand the sum you have 1/3 * N^3 + ...

You can see it simply by plotting the values of sum after running the algorithm for different values of N: enter image description here

Upvotes: 6

Related Questions