CODEWITHSUNDEEP
algorithmloopsbig-o
IronHao
IronHao

Reputation: 13

Determining the big-O of this loop question

I'm not sure about the big-O cost of this loop. Can anyone help me? I will comment about what I think.

sum = 0;  // O(1)
for(i=0;i<N;i++)
  for(j=0;j<i*i;j++)
    for(k=0;k<j;k++)  // run as 0+1²+2²+...+n²= n(n+1)(2n+1)/6
      sum++;  //  O(1)

My guess is O(N^3). Is that correct?

Upvotes: 1

Views: 52

Answers (1)

logi-kal
logi-kal

Reputation: 7880

Your 0+1²+2²+...+n² steps estimation is wrong.

The innermost loop runs exactly 0+1⁴+2⁴+...+(N-1)⁴ times. This is the sum of the first n-1 numbers to the power of four, that is equal to n(n-1)(6(n-1)³+9(n-1)²+n-2)/30.

Thus the total cost is O(N5).

Follows another way of reaching the same result.

  • The outer loop runs exactly N times.
  • The middle loop runs up to i*i times (i.e. at most N2 times) for each outer iteration.
  • The inner loop runs up to j times (i.e. at most N2 times) for each middle iteration.

Multiplying the cost estimations, the total cost is O(N5).

Upvotes: 3

Related Questions