Big O

This is a discussion on Big O within the C++ Programming forums, part of the General Programming Boards category; Algorithm Form Running time for(i=a; i<=b; i++){ 0(1) //Loop body requiring //Constant time } for(i=a; i<=N; i++){ 0(N) Linear time ...

  1. #1
    Registered User
    Join Date
    Aug 2001
    Posts
    84

    Big O

    Algorithm Form Running time

    for(i=a; i<=b; i++){ 0(1)
    //Loop body requiring
    //Constant time
    }


    for(i=a; i<=N; i++){ 0(N) Linear time
    //Loop body requiring
    //Constant time
    }

    This is a example in a book but I do not see why the first loop is
    faster then the second?

  2. #2
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    You need to remember that O notation isn't a measure

    of speed but of rate of growth. If you look at the first one as N increases

    the number of times the loop is excuted (b - a + 1) remains the same.

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    156
    Nick,

    Could you expand on that a little. I'm not following.

  4. #4
    Registered User
    Join Date
    Aug 2001
    Posts
    84

    I can only expand with another question?

    for(i=a; i<=N; i++) 0(N^2)-Quadratic time
    for(j=b; j<=N; J++){
    //Loop body requiring
    //Constant time
    }

    for(i=a; i<=N; i++) { O(N*M)
    //Loop body requiring
    //time O(M)
    }

    I understand the first for loop and the Big O notation but I do not understand why the second for loop is (N*M)?

  5. #5
    Unregistered
    Guest

    Lightbulb Little more clarification

    This information assumes that N is the unknown or variable quantity.

    Code:
    for(i=a; i<=N; i++) 0(N^2)-Quadratic time 
       for(j=b; j<=N; J++){ 
       //Loop body requiring 
       //Constant time 
    }
    This is O(N^2) because each loop of N runs N times regardless of what N is.

    Code:
    for(i=a; i<=N; i++) { O(N*M) 
       //Loop body requiring 
       //time O(M) 
    }
    This is based on the same principal as the first one except that M can be variable also. Generally this can be expressed as O(N^2), but since M doesn't have to be equal to N, it is usually more specifically expressed as O(N*M). When you are trying to graphically see which algorithm is better by plotting on a two-dimensional plane the Big-Oh expressions, you can't accurately plot y=NM like you are able to do with y=N^2.

    Code:
    for(i=a; i<=b; i++){ 0(1) 
       //Loop body requiring 
       //Constant time 
    }
    This code isn't based on N, so in terms of N it is constant time. The time doesn't vary based on N at all. Since the Big-Oh is usually based on N or one particular variable quantity, it is O(1). On the other hand, if you were to develop an actual expression to describe the runtime, it would be b-a+1. This just describes how many times the body of the loop will run for any integer values a and b.

    Hopefully this clears up a little bit regarding the Big-Oh discussion.

  6. #6
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Here are some more formal definitions but at this
    point you probably should just look at a
    procedure and guess without proving it.

    http://www.ics.uci.edu/~lueker/23/notation.pdf
    http://www.cs.hmc.edu/courses/2001/s...s140.lec01.pdf
    http://www.cs.uky.edu/~jurek/cs315/n...s05102001.html

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Any significant Big Endian Machines?
    By abachler in forum Tech Board
    Replies: 9
    Last Post: 01-29-2009, 12:53 PM
  2. How Big is Too Big
    By kpreston in forum C Programming
    Replies: 4
    Last Post: 10-25-2008, 10:16 AM
  3. Big and little endian
    By Cactus_Hugger in forum C Programming
    Replies: 4
    Last Post: 10-12-2005, 07:07 PM
  4. about big O notation
    By deepakkrmehta in forum C Programming
    Replies: 3
    Last Post: 08-27-2005, 02:31 PM
  5. Looking for some big C/C++ projects
    By C-Dumbie in forum C Programming
    Replies: 5
    Last Post: 09-16-2002, 12:18 AM

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