Results 1 to 10 of 10

Thread: Big-O Notation

  1. #1
    kraigballa is offline Senior Member
    Join Date
    Oct 2011
    Posts
    115
    Rep Power
    0

    Default Big-O Notation

    I have two problems that I think I know, but I'm not sure..


    b.
    Java Code:
    int N;
    // N is given a value
    int loopVar = N;
    while (loopVar>0) {
    System.out.println( loopVar);
    loopVar = loopVar / 2;
    }
    I would say O(log N)


    c.
    Java Code:
    int sum = 0;
    for (int i=0; i<n; i++)
    for (int j=0; j<i; j++)
    sum = sum + j;
    I would say O(N(log N)) or maybe O(N^2)

  2. #2
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    4,001
    Rep Power
    10

    Default Re: Big-O Notation

    The first one seems reasonable, but I'm not convinced you're right about the second one. Why don't you write a small program that runs through this, counting the number of times the sum is incremented compared to n?

    Hint- What would happen if your first loop was reversed (went from n-1 to 0 instead of 0 to n-1)?
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    kraigballa is offline Senior Member
    Join Date
    Oct 2011
    Posts
    115
    Rep Power
    0

    Default Re: Big-O Notation

    I ran it with a different counter in each loop. The first loop only counted 10 times, but the second (inner for loop) went 45 times. Total being 55...which without the inner for loop would be 10 = O(N), but seeing how this one has the inner loop I still think O(N(logN)) looks right..??

  4. #4
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    4,001
    Rep Power
    10

    Default Re: Big-O Notation

    Well, I don't think you're right. Where are you getting the logN from?
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  5. #5
    kraigballa is offline Senior Member
    Join Date
    Oct 2011
    Posts
    115
    Rep Power
    0

    Default Re: Big-O Notation

    Not really sure..it just seemed like it was 10 times larger than logN (Any algorithm which cuts the problem in half)...how would you get a logN??

  6. #6
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    4,001
    Rep Power
    10

    Default Re: Big-O Notation

    I didn't get a logN. Where does the second "algorithm" (really it's an implementation of an algorithm, but that might be a bit pedantic) cut the problem in half?

    Like I said, write a program that runs this algorithm with different values for N, and compare how many times you do go through the loop. You can even graph the values out to visualize the big-O curve.

    Or you could think about what the program is doing in general. What's it doing the first time through the outer loop? The inner loop? The second time? Draw it out on a piece of paper if it doesn't all fit in your head at once.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  7. #7
    kraigballa is offline Senior Member
    Join Date
    Oct 2011
    Posts
    115
    Rep Power
    0

    Default Re: Big-O Notation

    So the first time through the loop...

    Java Code:
    N       Outer      Inner
    1         1          0
    2         2          1
    3         3          3
    4         4          6
    5         5          10
    You're right, the outer is never cut by half, but the inner does slowly increase as n increases. Not sure how to figure out which notation it is using. at this point it seems to be O(N+j) which would be O(N)

  8. #8
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    4,001
    Rep Power
    10

    Default Re: Big-O Notation

    Using only small number for N isn't really in the spirit of algorithm analysis, and it doesn't give you much useful information. What happens when N is 10, 100, 1000, 100000? Graph it out to see a curve. Is that curve linear? Logarithmic? Quadratic? Something else?

    Hint: remember summations from one of the annoying math classes that were a prereq for this class?
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  9. #9
    kraigballa is offline Senior Member
    Join Date
    Oct 2011
    Posts
    115
    Rep Power
    0

    Default Re: Big-O Notation

    The problem is that when we get an exam we will only be given the code, and have to decide which algorithm it is. Are there tell-tell signs when it comes to what the code/loops look like?

  10. #10
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    4,001
    Rep Power
    10

    Default Re: Big-O Notation

    You have to look at the bigger picture. What is the general behavior of the algorithm? What does it do as N goes up? If you increase N by 1, how many more calculations are added? You can't always figure that out be looking at small values for N, unless you immediately recognize the pattern.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

Similar Threads

  1. += notation
    By sehudson in forum New To Java
    Replies: 2
    Last Post: 03-11-2011, 05:51 AM
  2. Big O notation
    By simorgh in forum Advanced Java
    Replies: 18
    Last Post: 07-10-2010, 04:26 PM
  3. Big O notation
    By vendetta in forum New To Java
    Replies: 6
    Last Post: 01-08-2010, 08:47 PM
  4. Big O Notation
    By dsym@comcast.net in forum New To Java
    Replies: 1
    Last Post: 02-21-2009, 07:02 PM
  5. Big Oh Notation and Heaps
    By gibsonrocker800 in forum Advanced Java
    Replies: 8
    Last Post: 01-25-2008, 11:06 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •