Skip to main content

Posts

Showing posts from February, 2011

Big-O

And now for Big-O notation.  It's not about mecha and it involves math... don't worry I'll keep the math light. Big-O notation is a measure of an algorithms scaling based on input size.  Every operation on a data structure is an algorithm and Big-O lets us know how expensive they are going to be. As an example lets look at a stack of cards. Picking the top card off of a stack of cards takes the same amount of time if there are 6 cards in the stack or 600 cards in the stack.  This only every takes 1 operation regardless of the size of the stack so this is O(1).  The operation is constant.  Even if the stack was in a box which needed to be opened first, hence taking 2 operations, this would still be O(1) because it doesn't grow with input size. Finding a specific card in the stack is more difficult in a stack of 600 than in a stack of 6 however. On average you have to look at 3 cards on the stack of 6 and 300 cards on the stack of 600.  This means that on average you