OK, O-Notation for Real (not really)

In our last installment we learned a number of important things. Mainly, we learned that I’m a liar. I promised O-notation and I delivered crude jokes. Sorry.

O-Notation, for real

So let’s actually look at O-notation. Wikipedia is always good for things like this. Looking at Wikipedia’s page about O-notation we find that:

Let f(x) and g(x) be two functions defined on some subset of the real numbers. One writes

insert image from wikipedia…

OK, so wiki is actually incredibly annoying to quote, since it uses images rather than text. I’m going to start over and translate the pictures to text:

Let f(x) and g(x) be two functions defined on some subset of the real numbers. One writes

f(x)=O(g(x)) as x goes to infinity if and only if for sufficiently large values of x, f(x) is at most a constant multiplied by g(x) in absolute value.

That is, f(x)=O(g(x)) if and only if there exists a positive real number M and a real number X0 such that abs(f(x)) <= M*abs(g(x)) for all x greater than X0.

So there you go… O-notation is simple. Wiki explains everything. My blogging career is over. Except…

Lolwut?

I’m sure that some of you find the above wiki explanation pretty simple. We’ll be doing denotational semantics in a couple years. You should come back for that.

I’m also sure that some of my target audience is looking at the wiki definition of big-O notation and saying “lolwut?” Don’t worry. In the end we will unpack the wiki definition and own it. But before we do that we will build a bit of intuition. If the wiki definition of big O notation makes no sense to you right now, don’t worry. It will.

## Everything You Need to Know About O-Notation (Not really) In One Sexist Joke

Everything You Need to Know About O-Notation (Not really) In One Sexist Joke

I have a lot of friends who are programmers, but who never studied computer science formally. Every once in a while one of them asks me about big-O notation. I’ve been asked about this by people who hold management positions at prominent web companies. I’ve always found this surprising. It is important to understand the notation, but it is more important to understand the idea behind it. So I am going to explain the big idea using an old sexist joke. The more sensitive among you might want to avert your eyes.

Back in the bad old days, when women could only work as secretaries, two lawyers opened a law firm. Their first order of business was to find a suitable receptionist (this was back in the days when you needed to have clerical help to get anything done, and there was no voice-mail.) They put an ad in the paper and started interviewing candidates.

One day, an incredibly beautiful and correspondingly stupid candidate came in to interview, and they hired her on the spot. I could write odes to her hair, her heaving breast, etc. I won’t though- let’s just say that she was hawt….

The next day Partner B came in a bit late and asked Partner A how their new receptionist was working out. “Well,” he said “I’d certainly like to father her children, but I’m not so sure about her as a receptionist. I asked her to look up Mr Higginbotham’s number this morning. After an hour I went out and found her bent over the phone book. I asked her how it was coming and she said ‘Great- I’m already up to the G’s.’”

OK, let’s let the general hilarity/offense subside and note that Ms. heaving-bosom pursued a sub-optimal strategy in looking up a phone number. This should be obvious to anyone who has ever used a phone book. But programmers far too often do essentially the same thing without realizing it. So it is worth thinking about where our fictional receptionist went wrong.

What is an Algorithm?

Let’s say we want to do something with some data. Let’s say our data is the phone book. We might want to find someone’s number, given a phone book. How should we go about it?

An algorithm is a description of an operation performed on data. In other words, any description of a method of finding a phone number in a phone book is an algorithm. There are lots of ways of finding a phone number in a phone book. Let’s look at a few:

Random Access: Assume that every entry in the phone book has a number associated with it. Maybe the first entry is 0, the next is 1, etc. Let’s also assume we know what the largest number associated with any name/number pair is. We can search for “John Smith”’s number by generating random numbers and looking at the corresponding entries in the phone book until we get John Smith. It should be noted that we are never guaranteed to get his entry if our numbers are really random. So this is probably not a very good method for finding phone numbers.

Linear Search: We can look at every entry in our phone book starting at the beginning. This is better than random, because we know that we will either find John’s number, or we will conclude that it is not in the book. In fact we can start to talk about how many steps it will take to perform this algorithm. If we know that John is in the book we will generally have to look at about half the entries in the book in order to find him. At worst, if John is not in the book, we will have to look at every entry to be sure of that. This is what our receptionist was doing and anyone who has used a phone book knows that we can do better:

Binary Search: We know the phone book is arranged alphabetically. Because we know this we can look at the middle entry and figure out if John is in the second half of the book or if he is in the first half. We can treat the half we have chosen as a new phone book and divide it again. We will zero in on John’s number very quickly by doing this, even if the phone book is large.

We can again talk about how many entries we will have to look at, though it is not quite as simple as it was in the linear case. We will have to look at entries proportional to the log base 2 of the number of entries in the phone book. If that isn’t immediately clear to you don’t worry. It will be by the time we get done looking at this stuff.

OK, so.. What is an Algorithm?

The three methods of finding a number in the phone book I described are algorithms. I want to emphasize this, so I am repeating it. Imagine that you have an unfrozen caveman lawyer on your hands and that he has to learn to use a phone book. Depending on how well he has learned the alphabet you might tell him to use any of the three methods I described above. In telling him how to use any of them you would define an algorithm.

So how can we characterize algorithms?

I’m glad you asked. It seems intuitively obvious that binary search is better than linear search. I mean, given the Manhattan phone book, and a name you want to find in it, we both know which you will use. But a skeptic might point out that a fast computer could do a linear search of the Manhattan phone book faster than you can do a binary search. Does this mean that the speed of the device is more important than the algorithm? Tune in next time to get a partial answer.

So You Lied About Explaining O-Notation?

Well, that depends on what you mean by lie, but.. yes. Sorry. Let’s talk about O-Notation next time, OK?