My intent is to make this blog accessible to software amateurs, but many readers will probably have heard this stuff before. Hopefully I can at least make the description entertaining, because I think it's an important one to be familiar with. If you happen to be one of those people who dimly remembers this topic from your "Intro to Computer Science" class, but forgot it promptly, it's time to learn it again. It matters.
Job interviewers often ask questions where they require you to make up a program that solves a programming puzzle. I have impressed the hell out of numerous interviewers by making up a solution, analyzing the solution in Big O, and then coming up with a more efficient solution. I didn't always get those jobs, but the feedback was always "You seem like an excellent candidate, very solid on the fundamentals, but you don't know enough of the specific technologies we work with." When I got the job at Digital Motorworks last year, the director of engineering flat-out told me that mine was the best answer he ever heard to his question. So pay attention!
A "dumb" dictionary search
Suppose you are looking for a word in a printed dictionary. There are two ways you can do it, a dumb way and a smart way. The dumb way is: read the first word. Is that the word you want? No. Go to the next word. Is that the word you want? No. Go to the next word. And so on.
I just looked up how many words are in a typical dictionary. It's about 170,000. So how long will it take you to find the word you want? Well, it depends, of course. If you are looking for "aardvark," then you will have to look at only one word, or just a few. If you are looking for "zymurgy," then you will have to look at nearly all 170,000. On average, you can expect to read through 85,000 words: half of 170,000.
Nobody reads the dictionary that way, of course. Think about how you would really look up a word, such as "program." Open the book to the middle. You find the word "mouse." That is before the word you want, so divide the right side of the dictionary in half, pick another page, and look again. "Teacher." That is after the word you want, so divide the space between "mouse" and "teacher" in half and look again. And so on.
This technique is much more efficient than the dumb search, because it takes advantage of the fact that the dictionary is sorted for you. How long does it take? When you first open the dictionary, you are splitting the search space in half: instead of 170,000 words, you now have 85,000 words to look at. Then you split the search space in half again. With each page turn, you divide the number of words remaining for you to look at. So here's how it goes:
170,000 is a very specific number of words for a dictionary to have, so let's generalize this. The number of words in the dictionary is "n". How long did the dumb search take? We read on the order of n/2 words. Therefore, we say that solution took O(n/2) operations. That's all "Big O" means: "O" stands for "Order of." Nothing magical here, right?
How about the smart search? It took 18 searches, because
218 > 170,000
(17 wouldn't be enough. Check.) If you fiddle with that equation, you'll find that
18 > log2 170,000
So, to speak more generally, the smart dictionary search is O(log2 n).
With me so far? Now I'm going to get slightly tricky.
When I said the dumb search was O(n/2), the "/2" part is a constant multiplier: it represents the number 1/2, which is always the same. You take O(n) and you multiply it by one half. But really, we don't need to be that specific. We don't know exactly how long each of the operations will take, so when we are estimating compute time, it's pointless to factor in a constant. For instance, if you do 100 operations that each take half a second, or you do 50 operations that each take a whole second, it amounts to the same thing.
So, by convention, we ignore constant multipliers and don't include them. Instead of saying that the dumb search is O(n/2), let's just say that it takes O(n); all we care about is finding the right order of magnitude anyway.
Similarly, I said the smart search takes O(log2 n). But the "2" subscript in "log2" is unnecessarily specific too; all we care about is that it's a log. So the smart search is O(log n) time.
Why should you care?
Let's consider some specific values of "n" and see how much time we save by using an O(log n) search instead of an O(n) search.
n=10 -> log n=1
n=100 -> log n=2
n=1,000 -> log n=3
n=10,000 -> log n=4
n=100,000 -> log n = 5
n=1,000,000 -> log n = 6
Obviously, if you are searching ten values, you can probably get away with scanning the entire list, but if you are searching a million values, you would rather have it take about 6 reads instead of a million.
As obvious as that is when I put it like that, I can tell you that there are a distressingly high number of times when I've sat down and analyzed code to discover that something which should easily take O(log n) time is written in such a way that it takes O(n) or even O(n2). The reason for this is that the guy who came before me started out with a small list of items, and then failed to plan for a time when the data would grow out of control to a thousand items or more.
You should be planning for this stuff up front. You should be asking yourself "How many values am I dealing with now? How many values can I imagine dealing with in the future?" If your program is dealing with information about cars, for example, you should think about how many cars there are in the world, and what fraction of those cars will eventually be in your database if you're a big success.
Remember that if you don't plan for this, you will have to put in the effort to change it. But also, by the time it gets to that point, you will have forgotten where the O(n2) function is, so you'll have to put in the effort of finding it and decoding the logic too. That's why you want to be mindful of future bottlenecks for your code as early as possible.
Next time I get around to posting about Big O, I'll be writing a little about sorting routines, interview challenges, and strategies to make basic logic more efficient -- some or all of those, as time and post length allow.