Programmers Dojo

Jeff Vitter is the provost and executive vice chancellor and the Roy A. Roberts Distinguished Professor at the University of Kansas. I just stumbled across his page and found a great book on external memory algorithms and data structures external memory algorithms and data structures. IE: algorithms and data structures to use when your dataset is too large to fit in main memory. He has many other papers on his site including several on external memory graph algorithms. Here's the link... http://www.ittc.ku.edu/~jsv/Papers/catalog/

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 o...