Big-Oh notation for code fragment

I am lost on these code fragments and finding a hard time to find any other similar examples.

//Code fragment 1  
sum = 0;  
for(i = 0;i < n; i++)  
 for(J=1;j<i*i;J++)    
   for(K=0;k<j;k++)
    sum++;

I'm guessing it is O(n^4) for fragment 1.

//Code fragment 2
sum = 0;
for( 1; i < n; i++ )
 for (j =1;,j < i * i; j++)
  if开发者_运维问答( j % i == 0 )
   for( k = 0; k < j; k++)
     sum++;

I am very lost on this one. Not sure how does the if statement affects the loop.

Thank you for the help head of time!

---

The first one is in fact O(n^5). The sum++ line is executed 1^4 times, then 2^4 times, then 3^4, and so on. The sum of powers-of-k has a term in n^(k+1) (see e.g. Faulhaber's formula), so in this case n^5.

For the second one, the way to think about it is that the inner loop only executes when j is a multiple of i. So the second loop may as well be written for (j = 1; j < i * i; j+=i). But this is the same as for (j = 1; j < i; j++). So we now have a sequence of cubes, rather than powers-of-4. The highest term is therefore n^4.

---

I'm fairly sure the 1st fragment is actually O(n^5).

Because:

n times,

i^2 times, where i is actually half of n (average i for the case, since for each x there is a corresponding n-x that sum to 2n) Which is therefore n^2 / 4 times. (a times)

Then, a times again,

and when you do: n*a*a, or n*n*n/4*n*n/4 = n^5 / 16, or O(n^5)

I believe the second is O(4), because:

It's iterated n times.

Then it's iterated n*n times, (literally n*n/4, but not in O notation)

Then only 1/n are let through by the if (I can't remember how I got this)

Then n*n are repeated.

So, n*n*n*n*n/n = n^4.

---

With a sum so handy to compute, you could run these for n=10, n=50, and so on, and just look which of O(N^2), O(N^3), O(N^4), O(N^6) is a better match. (Note that the index for the inner-most loop also runs to n*n...)

---

First off I agree with your assumption for the first scenario. Here is my breakdown for the second.

The If statement will cause the last loop to run only half of the time since an odd value for i*i will only lead to the third inner loop for prime values that i*i can be decomposed into. Bottom line in big-O we ignore constants so I think your looking at O(n^3).