Reputation: 10581
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
Reputation: 794
Another way to look at it is to use the "worst case" analysis. Originally, we have:
for
loop will run N
timesfor
loop will run i*i
timesThis 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:
for
loop will run N
timesfor
loop will run N*N
timesAnd the time complexity of this situation is of course O(N³).
Upvotes: 1
Reputation: 339
you can always use the intuitive way.
. . .
you can see the pattern easily. it is (nˆ2)*(n-1) therefore its big o should be O(nˆ3)
Upvotes: -1
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
:
Upvotes: 6