Big O Notation

This is a discussion on Big O Notation within the C Programming forums, part of the General Programming Boards category; I have some code snippets in which I have to find the run time using big O notation. code frag ...

  1. #1
    Registered User
    Join Date
    Jun 2009
    Posts
    28

    Big O Notation

    I have some code snippets in which I have to find the run time using big O notation.


    code frag 1:

    Code:
    void E(int array[], int N){
    int i, j;
    for(i=1; i<N-5; i++){
    
         for (j=i; j<i+5; j++)
         array[i] +=array[j];
       array[i] = array[i]/5;
    }
    }



    I understand the simpler ones such as O(N) and O(N^2), but this seems to be slightly more complex.

    could someone explain how we would arrive at an answer for this?

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You need to count how many times you will add things in. How many times will each for loop run?

  3. #3
    Registered User
    Join Date
    Jun 2009
    Posts
    28
    say if N was 10, the outside loop would run 5 times, and the inside loop would also run 5 times, so would it be O(5N)?

  4. #4
    Banned ಠ_ಠ's Avatar
    Join Date
    Mar 2009
    Posts
    687
    array subscripts start at 0 btw
    ╔╗╔══╦╗
    ║║║╔╗║║
    ║╚╣╚╝║╚╗
    ╚═╩══╩═╝

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by bigparker View Post
    say if N was 10, the outside loop would run 5 times, and the inside loop would also run 5 times, so would it be O(5N)?
    Because obviously 5 * 10 is 25.

    The point of big O is, how does the number of steps change, when N changes.

  6. #6
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    N is the number of elements. You need to determine what is done for each element. But not with constants such as 10, but like "nē" or "n * log(n)".

  7. #7
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Hint: if you look carefully, you'll notice that this inner loop
    Code:
         for (j=i; j<i+5; j++)
         array[i] +=array[j];
    always executes a constant number of times. Hence, the inner loop is O(1). Then just figure out the asymptotic bound for the outer loop, and multiply it by O(1), i.e. 1, and you'll get the asymptotic bound for the whole function.

    (It's like the fundamental counting principle. When you have loops that are one after the other, you can add their running times -- which in the context of big-Oh notation basically means that you can ignore whichever loop is less expensive. For nested loops, you can multiply the running time of inner loops by outer loops to get the overall running time.)
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  8. #8
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    if it was "j < n" or like that, the algorithm would run in O(n^2) time, since you have to do something for each element, which in turn is doing something for each element.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. big O notation question
    By l2u in forum C++ Programming
    Replies: 7
    Last Post: 11-08-2008, 02:53 PM
  2. about big O notation
    By deepakkrmehta in forum C Programming
    Replies: 3
    Last Post: 08-27-2005, 02:31 PM
  3. Big Oh notation, help me notate this
    By Jeremy G in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 05-12-2005, 03:27 PM
  4. big o notation
    By heat511 in forum C++ Programming
    Replies: 5
    Last Post: 04-19-2002, 11:27 AM
  5. Big O Notation
    By Drew in forum C++ Programming
    Replies: 1
    Last Post: 09-30-2001, 01:22 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21