Results 1 to 4 of 4
Like Tree1Likes
  • 1 Post By JosAH

Thread: Help with Big O notation

  1. #1
    Steve911 is offline Member
    Join Date
    Dec 2012
    Posts
    1
    Rep Power
    0

    Default Help with Big O notation

    I must learn how to find the Big O notation for 10 codes as the following:

    2 minutes/question. what is a good technique to do so? what is the Big O'notation for the following code?

    Give the Big O notation for the following function.



    public static void notationFunction(int arr[], int length)
    {
    System.out.println(“\nThis function is sweet”);
    for(int i = 0;i<length;i++)
    {
    System.out.println(“Arr[“ + i + “] = “ + arr[i]);
    }
    System.out.println(“Is this function order N?”);
    System.out.println(“maybe...”);
    for (int i = 0;i<100000;i++)
    {
    System.out.println(“Arr[“ + 0 + “] = ” + arr[0]);
    }
    for(int i = 0;i<length;i++)
    {
    for(int j = 0;j<length;j++)
    {
    System.out.println(“stuff”);
    }
    }
    int temp;
    for ( int j = 0; j < length; j++ )
    for(int y=0; y < length; y++)
    {
    for ( int k =0; k < length-1-y; k++ )
    if(arr[k]>arr[k+1])
    {
    temp = arr[k+1];
    arr[k+1] = arr[k];
    arr[k] = temp;
    }

    }
    for(int i = 0;i<length;i++)
    {
    System.out.println(“Arr[“ + i + “] = “ + arr[i]);
    }
    }

  2. #2
    mxcnrawker is offline Member
    Join Date
    Apr 2012
    Location
    San Jose Ca
    Posts
    16
    Rep Power
    0

    Default Re: Help with Big O notation

    first, you need to wrap the code

    [CODE]

    ......

    [CODE]

    so we can throughly read it and give you pointers, but the best things in general:
    - all primitive statements: prints are all O(1)
    - all loops are O(n)
    - all nested loops are O(n * m *...*q); where n,n,...q could be any variable, if they are all the same iterations then O(n**k) where k is a power := number of loops
    NOTE: assuming the loops go through the entire list
    else:
    O(k) where k is a positive integer, which is the number of iterations it goes through
    just practice and check out videos online or check your discrete mathematics book for references. Good luck

  3. #3
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,729
    Blog Entries
    7
    Rep Power
    21

    Default Re: Help with Big O notation

    Quote Originally Posted by mxcnrawker View Post
    - all loops are O(n)
    A O(log(n)) loop:

    Java Code:
    for (int i= 1; (i<<= 1) < n; ) ...
    A O(n*n) loop:

    Java Code:
    for (int i= 1; i < n*n; i++ ) ...
    etc. etc.

    kind regards,

    Jos
    quad64bit likes this.
    cenosillicaphobia: the fear for an empty beer glass

  4. #4
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default Re: Help with Big O notation

    Also, even something as trivial as a print can be something other than O(1) if the thing being printed is the result of a method which is not O(1). I assume you meant printing things like strings, but a blanket statement like
    prints are all O(1)
    is misleading.

    OP, this looks like a homework dump. Figuring this stuff out is the assignment, and usually needs to be done by hand. You need to derive a basic formula for the number of times something happens in a code block and simplify that to big oh notation.

    mxcnrawker hinted at the basic idea, and Jos pointed out some of the great examples of where general rules fail.

    You need to look at the input and outputs of the code block and see how often something is actually happening.

Similar Threads

  1. The Big O Notation
    By dougie1809 in forum New To Java
    Replies: 13
    Last Post: 04-23-2012, 10:39 PM
  2. Big-O Notation
    By kraigballa in forum New To Java
    Replies: 9
    Last Post: 02-23-2012, 03:17 AM
  3. += notation
    By sehudson in forum New To Java
    Replies: 2
    Last Post: 03-11-2011, 05:51 AM
  4. Big O notation
    By simorgh in forum Advanced Java
    Replies: 18
    Last Post: 07-10-2010, 04:26 PM
  5. Big O Notation
    By dsym@comcast.net in forum New To Java
    Replies: 1
    Last Post: 02-21-2009, 07:02 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
  •