1. Big-O Notation Problem

Given the fragment:
Code:
for(int i=0; i < n; i++)
for(int j=0; j < (n*n); j++)
for(int k=0;k < j; k++)
sum++;
Find the Big-O notation.

I'm having a little trouble with this. I know that the outer loop is going to run n times, the second inner loop will run n^2 times, but I'm not sure about the third inner loop. I'm guessing this is O(n^3) since there are three nested loops, but I don't think that's right. Can someone explain this to me?

2. Originally Posted by Sentral
I'm having a little trouble with this. I know that the outer loop is going to run n times,
Not much of a CS person (so don't trust me!) but I believe that is the answer here -- O(n) -- since n is the number of times this snippet must run to complete it's goal.

Otherwise I agree with O(n^3) since if n is 2 sum will be 8 (or maybe 7, I didn't test this...).

3. Do you mean how much one instance of the loop will take, or the whole code at once?

One go-round of the inner loop is quite obviously O(j). The first time j is 0, then 1, then 2, then 3, then 4, then 5, then ..., then n*n. So one go-round of the middle loop will involve (0+1+2+3+4+5+...+n*n) operations.

And then the outer loop will run the middle loop n times (since the middle loop doesn't depend on i in any way shape or form, it will run exactly the same way each time). So take the number from above and multiply by n.

4. Originally Posted by tabstop
Do you mean how much one instance of the loop will take, or the whole code at once?

One go-round of the inner loop is quite obviously O(j). The first time j is 0, then 1, then 2, then 3, then 4, then 5, then ..., then n*n. So one go-round of the middle loop will involve (0+1+2+3+4+5+...+n*n) operations.

And then the outer loop will run the middle loop n times (since the middle loop doesn't depend on i in any way shape or form, it will run exactly the same way each time). So take the number from above and multiply by n.
I have to find the Big-O of this fragment, so it doesn't matter how much one instance will take, I just need to know the upper bounds of the run time.

I'm still confused. I think if the fragment was just the first two loops the order would be O(n^3) since it's n * n * n= n^3. But adding the third loop in there confuses me.

5. Originally Posted by Sentral
I'm still confused. I think if the fragment was just the first two loops the order would be O(n^3) since it's n * n * n= n^3. But adding the third loop in there confuses me.
Yes but the actual measure is n, which if n=6, the loop occurs 6 times, not 216 times, so O(n). sum may be incremented 216 times but the measure is based on the number of something (n), whatever that significant something is.

6. Originally Posted by Sentral
I have to find the Big-O of this fragment, so it doesn't matter how much one instance will take, I just need to know the upper bounds of the run time.

I'm still confused. I think if the fragment was just the first two loops the order would be O(n^3) since it's n * n * n= n^3.
That's correct -- the inner loop always would take n*n, and it would run n times.

Originally Posted by Sentral
But adding the third loop in there confuses me.
Since it's easier than the other two loops, you were probably confused to start. This sort of thing is always addition -- for instance, your two loops above is actually n^2 + n^2 + n^2 + ... + n^2. But since you're adding the same thing a bunch of times, we use multiplication as a short cut. Here we're not adding the same thing, but different things, so you actually have to add: The first time you do the inner loop it will execute 0 times (because that's what j is), then 1 time, then 2 times, then ..., then n^2 times. So you need to add all those together. Then i will change and you do it again (here, since the inner loops don't depend on i, it will be the same value as before). Then i will change and you do it again and add it in.

Since 1+2+...+n^2 = (n^4-n^2)/2, the inner two loops (by themselves, not counting the outside i loop) will be O(n^4). Since the inner loops will run exactly n times, in exactly the same way (since they don't depend on i), so the whole fragment will run (n^5-n^3)/2 times, which is O(n^5).

7. Originally Posted by Sentral
Given the fragment:
Code:
for(int i=0; i < n; i++)
for(int j=0; j < (n*n); j++)
for(int k=0;k < j; k++)
sum++;
Find the Big-O notation.

I'm having a little trouble with this. I know that the outer loop is going to run n times, the second inner loop will run n^2 times, but I'm not sure about the third inner loop. I'm guessing this is O(n^3) since there are three nested loops, but I don't think that's right. Can someone explain this to me?
The loop is O(n^5). Because big-O is an upper limit, you need to examine the worst-behavior of the inner loop. When j is equal to n*n-1, the inner loop will execute n*n-2 times. That's worth n*n, as far as big-O is concerned. So the other loop of n times the internal loop of n*n times the inner loop of (worst case) n*n gives O(n^5).

You can always give a tighter bound for big-O if you want, so long as it is still correct. You often see very precisely-specified big-O bounds given in research papers, but these bounds can be simplified greatly while still remaining valid.

(BTW, O(n^x) is usually considered inefficient for x greater than 3, except for problems which are superficially exponential, in which case a speedup to any polynomial factor is usually considered significant)

8. Wait, wouldn't it be O(n^3 + T(n^2) ) where T(n) = n(n+1)/2, since the third loop is of an increasing size, and is not run n^2 every iteration through the main loop?

T(n)

9. n(n+1)/2 is O(n^2)

And since it is not + but * we get O(n^3*n^2) = O(n^5)

10. Originally Posted by vart
n(n+1)/2 is O(n^2)

And since it is not + but * we get O(n^3*n^2) = O(n^5)
Yeah, I realized my mistake with the + right after I posted, but got distracted by other things(50cents for gatorade in the vending machine downstairs!).

Fair enough. O(n^5) it is.

11. Originally Posted by vart
n(n+1)/2 is O(n^2)
To see why, distribute through the multiplication to get 1/2*(n^2+n). The constant factor 1/2 goes away, and the n^2 eats the n term, so the overall complexity is O(n^2)

12. I'm having trouble with another problem if someone can help me. It's just a variation on the previous problem. I still have to find the Big-O of the fragment.
Code:
	for(int i = 1; i <= n; i++)
for(int j = 1; j <= (i * i); j++)
if(j % i == 0)
for(int k = 0; k < j; k++)
sum++;
What's confusing me is the if statement. I'm pretty sure the order of magnitude should be lower since the if statement is stopping the inner loop from executing most times. I just don't know how to incorporate that if statement into my calculations. Would I subtract from my order? I know that the outer loop runs n times. Then the innermost loop runs i^2 times, but then the if statement confuses me.

13. The first loop runs n times. The second loop runs i^2 times. The third loop runs j times, but it doesn't always run -- it only runs when j is a multiple of i. Since the loop runs to i^2, that will happen i times.

If you're not good at thinking, then you're going to have to be good at picking arbitrary numbers, actually doing the code, and figuring out a pattern from that. For instance, say n is 4. Then you have this:
i = 1 -- j = 1: if true, sum++ happens one time
i = 2 -- j = 1: if false; j=2: if true, sum++ happens twice; j = 3: if false; j = 4: if true, sum++happens four times
i = 3 -- if true when j = 3, 6, 9, so sum++ happens 3, 6, 9 times
i = 4 -- if true when j = 4, 8, 12, 16, so sum++ happens 4, 8, 12, 16 times.

Add it all up 1 + (2+4) + (3+6+9) + (4+8+12+16). You should be able to find the formula for the parenthesized sums, and then find the formula for the grand total.

14. Ok, so I get 1 + 6 + 18 + 40= 65, but I don't see how this will help me. Are you saying that I need to find the summation formula for this, and that will give me by Big-O? I don't understand.

15. Originally Posted by Sentral
Ok, so I get 1 + 6 + 18 + 40= 65, but I don't see how this will help me. Are you saying that I need to find the summation formula for this, and that will give me by Big-O? I don't understand.
If you actually do the sums yourself, you've already lost. You should be able to see the patterns that gets you to
Code:
$\sum_{i=1}^{n} \sum_{j=1}^{i} ji$
that is, you sum one multiple of one, two multiples of two, three multiples of three, four multiples of four, and so on.