Printable View
Given the fragment:Find the Big-O notation.Code:for(int i=0; i < n; i++)
for(int j=0; j < (n*n); j++)
for(int k=0;k < j; k++)
sum++;
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?
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.Quote:
Originally Posted by Sentral
Otherwise I agree with O(n^3) since if n is 2 sum will be 8 (or maybe 7, I didn't test this...).
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.Quote:
Originally Posted by tabstop
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.Quote:
Originally Posted by Sentral
That's correct -- the inner loop always would take n*n, and it would run n times.Quote:
Originally Posted by Sentral
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.Quote:
Originally Posted by Sentral
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).
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).Quote:
Originally Posted by Sentral
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)
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)
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!).Quote:
Originally Posted by vart
Fair enough. O(n^5) it is.
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)Quote:
Originally Posted by vart
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.
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.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++;
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.
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 toQuote:
Originally Posted by Sentral
that is, you sum one multiple of one, two multiples of two, three multiples of three, four multiples of four, and so on.Code:\[
\sum_{i=1}^{n} \sum_{j=1}^{i} ji
\]
Hm ok, I see that now. But how does this lead me to finding the Big-O notation? I thought usually this type of thing ends up in a summation formula that you multiply out and find the largest degree, but I don't see this happening. What does your notation mean? Is that supposed to be summation?
Since that's what it says, I'm going to say "yes". (Edit: Thanks to David Hausheer's LaTeX2PNG.)Quote:
Originally Posted by Sentral
Ok wow, I've never seen a summation like that before. I don't know how to figure out this big-o stuff. Is that summation inside summation? Ugh this is confusing.
Hm, assuming you want me to expand that I get this http://hausheer.osola.com/latex2png/...0/0/result.png
So my Big-O is O(n^2) ?
Well, once you get to page ten of the book, it's amazing what you see. But just like everything else you work it from the inside to the outside.
So by definition you cannot have i or j in your answer, since they're the variables of summation. Look at it: the first summation isQuote:
Originally Posted by Sentral
Now that gets summed as i goes from one to n.Code:$\sum_{j=1}^{i} ji = i\sum_{j=1}^{i} j = i((i^2+i)/2) = (i^3+i^2)/2$.
Edit: Or if you want it to look a little better:
Code:$\sum_{j=1}^{i} ji = i\sum_{j=1}^{i} j = i\frac{i^2+i}{2} = \frac{i^3+i^2}{2}$.
Ok, I finally think I got it. This is my final answer.
O(n^4)Code:(1/8)*n^4+(5/12)*n^3+(3/8)*n^2+(1/12)*n