Measuring Speed: How Fast is Fast?
When we talk about data structures and algorithms, we need a way to measure exactly how fast they are. Computer processors get faster over time, but that doesn't mean that an algorithm that was invented in the 80s is better now, even if we CAN search many times faster!
In computer science, we measure algorithms by how many steps they take relative to the size of the input. To do this, we use what is called Big O (pronounced "big oh") notation, which counts the number of steps and then throws away everything except the largest factor. To see what that means, let's take an example.
Consider the problem of sorting a list of integers. One of the easiest ways (to program, at least) is called bubble sort. You compare the first two elements in the list, and swap them if the first one is higher. Then you compare the 2nd and 3rd elements in the list and swap them if element two is higher. You continue this way until you've worked your way through the entire list, at which point the largest element is at the end of the list. You then start over and do the same thing again, but stop at the 2nd to last position (which now contains the second largest element); continue the process until the entire list is sorted.
How long does this take? If the list has n elements, the first time through requires n-1 comparisons. The second time through requires n-2 comparisons, then n-3, and so on. If you add all of this up, you get (n2-n)/2 comparisons, or 1/2 n2 - 1/2 n. We throw away everything except the largest factor, and say that bubble sort runs in O(n2) time.
Other algorithms run much more quickly; for example, if we know that all of the numbers are between 1 and 100, we can use a bucket sort, which runs in linear, or O(n) time. For small sorts, we can't tell which algorithm is faster - the constant factors we threw out (such as the 1/2 multiplier for bubble sort) may overpower everything else. But with larger sorts, the algorithm with the lower big-oh runtime will perform better. If we have a million items to sort, for example, bubble sort will take approximately a million times as long as bucket sort!