Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: Big O notation... can you check my answers for each code segment?

  1. #1
    Member
    Join Date
    Mar 2013
    Posts
    58
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Big O notation... can you check my answers for each code segment?

    int sum = 0;
    for (int i = 0; i < n; i += 2)
    sum++; //I said this is O(log n) because if n=10 then this loop executes half the time. Not sure though. Or is it O(n)?

    int sum = 0;
    for (int i = 0; i < n; i++)
    sum++;
    for (int j = 0; j < n; j++)
    sum++; // I said O(n) for this one because it executes 2n times which is therefore O(n).

    int sum = 0;
    for (int i = 0; i < n; i++)
    for (int j = 0; j < n[SUP]2[/SUP]; j++)
    sum++; // my answer is O(n[SUP]3[/SUP])

    int sum = 0;
    for (int i = 0; i < n; i++)
    for (int j = 0; j < 2*i; j++)
    sum++; //I think this is O(n[SUP]2[/SUP])

    int sum = 0;
    for (int i = 0; i < n; i++)
    for (int j = 0; j < n2; j++)
    for (int k = 0; k < j; j++)
    sum++; //I think this is O(n[SUP]3[/SUP])

    int sum = 0;
    for (int i = 1; i <= n; i = i[SUP]2[/SUP])
    sum++; //and finally I think this one is O(log n)

    Could you correct me? I want to see how well I know this.


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Big O notation... can you check my answers for each code segment?

    1 is wrong. Hint: write out the expression for how many times the loop executes.

    3 I'm assuming you meant the inner loop to be 0 to n*n (a.k.a. n squared)? If so, yes it is n cubed.

    5 I think you have a typo in the actual code. Perhaps you meant this?

    int sum = 0;
    for (int i = 0; i < n; i++)
    for (int j = 0; j < n2; j++)
    for (int k = 0; k < j; k++)

    If so, you're not quite right because n2 does not have to equal n. Both terms should appear in the big O, though O(n^3) is not a bad approximation if n2 is approximately the same as n.

  3. The Following User Says Thank You to helloworld922 For This Useful Post:

    EDale (September 18th, 2013)

  4. #3
    Member
    Join Date
    Mar 2013
    Posts
    58
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Re: Big O notation... can you check my answers for each code segment?

    So for #1 if n=10 then the loop executes 5 times. So if it's not O(log n) then it must be O(n) because the number of times it executes is proportional to n? Is that right?

    #3 yes that's what I meant, I guess the code didn't work! Thank you.

    #5 so then it is O(n^2)? I'm a little lost, however thank you!

  5. #4
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Big O notation... can you check my answers for each code segment?

    The reasoning for 1 is a bit convoluted. It is O(n) because you are running it half the time: O(n/2). But big-O drops the constant factors, so we're left with O(n)

    #5 is not O(n^2). O(n^3) isn't a bad approximation, but it's a somewhat lazy answer. Read my hints about including n2 and n in the big-O (unless there were two typos in the original code).

  6. #5
    Junior Member
    Join Date
    Oct 2013
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Big O notation... can you check my answers for each code segment?

    O(log n) would basically be if each iteration you are dividing the remaining elements in half (i.e.- traversing a binary search tree). So an example of something that would look like O(log n) in a for loop could be:

    for(int i = 1; i <= n; i = i * 2)
    {
         //some code
    }

    if n was 32, i would progress as follows: 1, 2, 4, 8, 16, 32. Notice if there were 32 elements, it only took until the 5th iteration to get to 32. log (base 2) 32 = 5 or 2^5 = 32. Hence it is O(log n). Now this could change depending on what was in place of //some code. For instance, inside the loop, if you looked through the entire set of n elements (or had the potential to look through them all, say in a linear search) then you could say O(n log n). This was a very basic explanation but hopefully it makes at least O(log n) a little easier to understand.

Similar Threads

  1. Replies: 3
    Last Post: January 25th, 2013, 06:53 AM
  2. Big-O Notation question
    By colerelm in forum Java Theory & Questions
    Replies: 1
    Last Post: November 28th, 2011, 09:52 PM
  3. [SOLVED] Question about inline code segment
    By brighamandrew in forum Java Theory & Questions
    Replies: 2
    Last Post: September 1st, 2011, 04:40 AM
  4. Replies: 5
    Last Post: July 7th, 2011, 09:22 AM
  5. Compute the frequency count and big-oh notation for a certain code segment
    By maykel_trinidad in forum Java Theory & Questions
    Replies: 3
    Last Post: November 13th, 2009, 10:23 AM

Tags for this Thread