Big O Notation

I mentioned "Big O" notation in the "Splitting an Int" thread, and feared many readers wouldn't know what I was talking about. A google search didn't turn up any descriptions I cared for, so here I am, writing my own.

PS: If anyone who actually graduated from a CS program (as opposed to making it half-way through like me) spots some flaws in my understanding, please chime in.


"Big O" notation is a formal way of describing how efficient an algorithm is in general terms... in Orders of magnitude (which is where the O comes from). An order of magnitude is basically another digit in the number used to describe a value. 1, 10, 100, 1000, etc. If you happen to be using binary instead of decimal, an order of magnitude isn't quite as earth-shaking, but still nothing to sneaze at.

Lets start with an example.

int foo( int i )
{
  return i;
}

Not much going on there. No matter what you pass "foo", you'll always get the same execution time. That's big O of 1, written "O(1)". That's "constant time", which is the best there is as far as Big O is concerned. Big O doesn't say anything about HOW LONG that constant time might be, only that it is constant. That constant time could be 40 years or 2 nanoseconds, but so long as it's constant, it's O(1).

Moving on:

void bar( char **strs, int numStrs)
{
  for( int i = 0; i < numStrs; ++i) {
    printf( "%s\n", strs[i] );
  }
}

This function will take an ammount of time that is directly proportional to the ammount of stuff passed in (in this case an array of strings, but it could just as easily be anything: a linked list of game objects, an int, whatever).

As 'n' (numStrs in this example) grows, so grows our execution time. That's O(n). This is pretty decent, as far as Big O notation goes.

Up next we have O(n^2):

void baz( char ***strs, int numLists, int numStrs )
{
  for (int i = 0; i < numLists; ++i) {
    for( int j = 0; j < numStrs; ++j) {
      printf( "%d: %s\n", i, strs[i][j] );
    }
  }
}

The execution time of this function will be proportional to numLists * numStrs, but Big O doesn't care... it abstracts them away to a single value. O(n^2).

You can see how this is going. As you get deeper and deeper loops, you get bigger and bigger powers.

There are also Big O values that aren't straight powers of 'n'. They're based on the Log2(n). Searching a sorted array, or traversing a binary search tree are both examples of O(log2(n)). A sorted list of 16 elements will take at most 4 tests to find what you're after.

A binary sort takes O(n*log2(n))... which is quite an improvement over bubble-sort's O(n^2):

binary sort        bubble sort
   10:     40                 100       binary is about 2 times faster
  100:     700                10000     binary is now  around 14 times faster
 1000:     10000              1000000   binary is now 100 times faster
10000:     140000             100000000 binary is now about 700 time faster

Big O doesn't care about constant multipliers. If there are 40 functions, and each one is O(n), that's still O(n). There's no such thing in Big-O-ville as O(40n). Or O(n/2).

That about covers it.


When I was taught Big O, it was in a "discrete math" class. I memorized all the rules, but they made absolutely no sense to me. The next semester, I walked into my data structures class, and in the first 10 minutes, it all fell into place. The instructor gave some search example and said "This is O(n)". BANG. The light went on. By giving you examples along the way, I'm hoping most of you can skip the semester of memorization, and skip to the "I Get It".


Any questions class? There will be a short quiz next period.