Thread: determining big o, theta, omega?

  1. #1
    Registered User
    Join Date
    Dec 2004

    determining big o, theta, omega?

    how would i go about determining the big o, theta, and omega of a piece of code?

    i know assigning i = 0, j = 0, y = 0 is the constant 3 and becomes insignificant to big o. is while( i < 6 ) 6x? do i multiply everything in the loop by 6x?

    void asdf() {
      int i = 0, j = 0, y = 0;
      while( i < 6 ) {
      j = 0;
       while( j < 5 ) {
        y = x = j;
        y = x ^ y + i;
        printf("x = %d y = %d\n", x,y);
        j += 2;
       } ++i;

  2. #2
    Registered User
    Join Date
    Nov 2004
    well, let's see..
    first of all, the whole thing runs in constant time, since it is determined beforehand between which values the loops will iterate. So, the code runs in O(1) time. One could say that more specifically, it runs in O(18) time, since the outer loop iterates 6 times and the inner loops 3 times.
    But we can ignore "lower-order terms and constants", and just say it runs in O(1) time.
    O(1) is the upper bound of the function, meaning it won't run any slower than this. In this case, the functions running time is fixed, and thus we know that this is also the lower bound on the running time - it can't run any faster than O(1). This means that the code runs in big-omega(1).
    Being both big-oh and big-omega at the same time means the function is big-theta.

    If we pretend for a second that i and j are not bounded by 5 and 6 respectively, but dependent on the size of the input, it looks just a little different. Since there are two variables to take into account, it is said to run in O(ij) time. Since the loops always run from 0 to i or j, we know this is both an upper and a lower bound on the running time. only half of the values of j are used since it is incremented by 2, but that's a constant factor and doesn't matter. The function runs in big-theta (ij).

    If you want to determine big-oh more precisely than this, you're gonna have to wait a couple of hours, until I've woken up. I'm still half asleep.. =)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How Big is Too Big
    By kpreston in forum C Programming
    Replies: 4
    Last Post: 10-25-2008, 10:16 AM
  2. RSA: Do I need to use a big int package for this?
    By MrSteve in forum C Programming
    Replies: 3
    Last Post: 04-27-2008, 06:05 AM
  3. Big and little endian
    By Cactus_Hugger in forum C Programming
    Replies: 4
    Last Post: 10-12-2005, 07:07 PM
  4. Adding to a big char* for search engine
    By Landroid in forum C Programming
    Replies: 5
    Last Post: 03-03-2005, 07:16 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