Thread: Big-O Notation Problem

  1. #1
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719

    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?
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Sentral View Post
    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...).
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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. #4
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    Quote Originally Posted by tabstop View Post
    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.
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

  5. #5
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Sentral View Post
    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.
    Last edited by MK27; 09-06-2009 at 04:55 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Sentral View Post
    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.

    Quote Originally Posted by Sentral View Post
    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. #7
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Sentral View Post
    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)
    Last edited by brewbuck; 09-07-2009 at 12:06 AM.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  8. #8
    Registered User
    Join Date
    Jul 2009
    Posts
    50
    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. #9
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    n(n+1)/2 is O(n^2)

    And since it is not + but * we get O(n^3*n^2) = O(n^5)
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  10. #10
    Registered User
    Join Date
    Jul 2009
    Posts
    50
    Quote Originally Posted by vart View Post
    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. #11
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by vart View Post
    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)
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  12. #12
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    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.
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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. #14
    For Narnia! Sentral's Avatar
    Join Date
    May 2005
    Location
    Narnia
    Posts
    719
    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.
    Videogame Memories!
    A site dedicated to keeping videogame memories alive!

    http://www.videogamememories.com/
    Share your experiences with us now!

    "We will game forever!"

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Sentral View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  2. I have big problem with encryption by ASCII
    By LINUX in forum C++ Programming
    Replies: 7
    Last Post: 04-29-2007, 12:46 PM
  3. polish notation calc problem
    By deedlit in forum C Programming
    Replies: 6
    Last Post: 06-14-2004, 10:17 PM
  4. Need Big Solution For Small Problem
    By GrNxxDaY in forum C++ Programming
    Replies: 8
    Last Post: 08-01-2002, 03:23 AM
  5. problem with pointer notation in for-loop
    By sballew in forum C Programming
    Replies: 5
    Last Post: 09-30-2001, 06:28 PM