Big-O Notation 3: Showing off how you think

Some job interviewers ask you to describe your career history in great detail.  Some want you to to explain the most obscure facets of the language you'll be working with.  And some will give you a puzzle and ask you to design a program that solves it.

This last category is by far my favorite sort of opportunity in an interview.  I'm a programmer because I love solving puzzles, so showing off that love is far more likely to make me look good than struggling under pressure to remember whether it's ArrayList or Vector that is thread-safe.  (Tip: It's Vector.)

When you get asked a puzzle problem, remember above all else that the interviewer is much more keen to know how you think than whether you get the "right" answer.  There may be some specific technique that they are hoping you know.  But even if the answer is not immediately obvious, don't panic.  If you sit there and explain your reasoning, refining your technique out loud, you can make up a lot of ground by showing that you can think on your feet.

A good example is the question I got from the Director of Engineering at Digital Motorworks.  Not only did I get the job, but that portion of the interview went so smoothly that I wrote down the question, my answer, and his reaction to save for posterity.  Here is a recap of the problem:

You're responsible for implementing a method called "sumExists."  This method should read two arguments: an integer, and an array of integers.  The return value will be a boolean, which is true if and only if there exists some combination of two distinct elements in the array that sum to the original integer.

For instance, suppose you call the method in this way:
sumExists(5, [7, 1, 2, 6, 4])
The array contains the elements 1 and 4, and 1+4 = 5, so the method should return true.

I immediately jumped to the most obvious solution -- not because I expected it to be right, but because I wanted to find some answer quickly and then improve it.  I said:

"If you wanted to use brute force, you could just inspect every element of the array, and compare it to every other element of the array, and see if they sum to the first number.  But that would require you to perform O(n²) operations, which is dumb.  So I would like to find a better solution.

"Suppose that we sort the array.  That would take O(n*log n) time (QuickSort, remember?) to complete.  Where does that get us?  Well, then we could quickly find the largest number and the smallest number of the array and compare them to each other.  We'll put counters on the left and right ends of the array, and add those values.  If they add up to the target, then we're done.  (Note: in the example, the sorted array is [1, 2, 4, 6, 7].  The high and low numbers are 1 and 7, which add up to 8.  Too high.)

"If the resulting number is too high, then the biggest number must be too big.  So we'll move the right hand counter to the left and try adding a smaller number to the smallest.  On the other hand, if the sum is too low, then the smallest number must be too small.  So we'll move the left hand counter to the right and try again.

"By doing this we'll be able to test pairs of high and low numbers until either we find the sum we need, or the counters meet in the middle.  If the sum is correct then we return true.  Otherwise, return false.

"Scanning the list in this way requires only one pass, which takes O(n) time.  But the sort was already longer, it takes O(n*log n) time.  The time to scan a large array once would be much smaller than the time to sort, so we ignore that factor.  This solution takes O(n*log n) time."

As I said, I wrote down the response and saved it.  So this is more or less a direct quote: "I've been doing this for a long time, and there is not one person in a hundred who has given as thorough and correct an answer as you just did."

There were other difficulties with getting this job, based on my short experience with specific technologies.  I'm convinced, though, that this was the best part of my series of interviews, and it got my foot wedged pretty firmly in the door.

Writing software is fundamentally different from working on an assembly line.  You don't solve the same problem twice.  You don't write the same code twice.  If you are repeating yourself, then you are in some way failing to leverage past experience.  You should be moving the duplicated code into a common function, or a common library, or something, so you can stop working on problems that have already been solved, and get the business of making your program do something new and interesting.

Because of this non-repetitive approach, it's important to be able to think about every problem from multiple angles, to try and relate it to past experience and evaluate different kinds of solutions.  Big O Notation is one tool for being able to evaluate how you're doing.

Count on this

Let's switch things up a bit and just do something for fun.  How high can you count on your fingers? Ten, you say? Amateurs. I'm going to teach you how to count much, much higher... without even taking your shoes off.

However, you're going to have to learn to count in binary first. Again, this is a very basic topic to computer science students, but I hear that there are plenty of non-programmers who read this blog. For their benefit, I'm going to give a primer. If you already know binary, feel free to skip down to the next bold header.

How to count in binary

When you count by tens, the digits can be represented as wheels on the odometer of your car. The right-most wheel goes:

• 1, 2, 3, 4, 5, 6, 7, 8, 9…
  

Then what happens? There is no "10" printed on the wheel. So where do we go next? The rightmost wheel flips from "9" back to "0", and as that happens, it also pushes the next wheel up by 1. So you have a 1 and a 0, and that's ten.

• 11, 12, 13, 14, 15, 16, 17, 18, 19…
  

Then the first wheel again flips over from 9 to 0, which in turn advances the second wheel from 1 to 2. Twenty. Right? Don't tell me this is hard, my son Ben understands this and he's in first grade.

So anyway, things are pretty much the same from here on out, until we get up to:

• 97, 98, 99…
  

And now? Well, the first wheel flips to zero, which in turn advances the second wheel. But the second wheel is already maxed out at nine, so it flips to zero, which also advances the third wheel, so now that wheel reads "1". 1, 0, 0. A hundred. Got it?

Okay, that's base 10. Binary is a similar system, except that it's got a severe shortage of numerals. Whereas we were using all the numbers from zero to nine, in binary you only have two possible values: one, and zero. Like a light switch: on, or off. Circuit open, or circuit closed. That's how a computer works. But with just ones and zeroes, you can represent every positive integer if you have the patience.

Let's imagine we have an odometer like before, but this one has very small wheels. They flip from 0 to 1. Then they flip from 1 back to 0. When they flip to 0, they advance the next wheel. Okay?

So your odometer reads:

• 0: 00000
  

Advance the rightmost counter by one:

• 1: 00001
  

Advance the counter again, and it flips to zero while dragging the second wheel along:

• 2: 00010
  

So that's two. Ten is two, in binary. Makes perfect sense, right? Advance the right hand wheel one more.

• 3: 00011
  

Next time we advance, both of the first two wheels will advance the next one over.

• 4: 00100
  

One hundred is four. I think you can take it from here.

In base ten, every digit represents a value that is ten times the previous digit. So the first digit is worth one, the second digit is worth ten, the third digit is worth a hundred, the fourth is worth a thousand, and so on.

Similarly, in base two, every digit represents a value that is two times the previous digit.

• 1 -> 1
  
• 10 -> 2
  
• 100 -> 4
  
• 1000 -> 8
  
• 10000 -> 16
  

Makes sense, right? You can write out any string of ones and zeroes and figure out what number they represent in binary by adding up the digits. For example,

• 10110 = 16 + 4 + 2 = 22
  

Okay, here's the fun part.

How to count to 1,023 on your fingers

• Hold out your hands, palms upward. Now make them fists. No fingers are extended. That's zero.
  
• Extend your right thumb. The right-most digit is now set to "on". That's one.
  
• Close up your thumb, but extend your right index finger. That's two.
  
• Extend your thumb again, and also leave your index finger out. Three.
  
• Close up your thumb and index fingers, but then extend your middle finger. That's four. It is also an obscene gesture to most people, so if you're in public, make sure your hands are under a desk or something.
  

That's really all there is to it. The highest you can go with this system is 1111111111 in binary, which is 1,023 in regular counting (2¹⁰ - 1).

Other numbers that form obscene gestures to Americans: 128; 132

Numbers that may be obscene to Europeans: 6; 384; 390. They may also be interpreted as peace signs or a Richard Nixon impression.

What can you do with this? Not much. You can kill about ten to twenty minutes. You can also probably perform a cheap mind-reading trick if you have an accomplice who can also do it. ("I'm thinking of a number from one to a thousand." "583. I certainly wasn't paying attention to the funny way you're holding your hands.") And finally, you can waste a perfectly good afternoon writing a silly blog post.

By the way... if you DID take your shoes off, you could count to 1,048,575.

Big O Notation 2: Sorting

As a Card-Carrying Nerd (you have to mail away exactly 314 cereal box tops for your card) I find entertainment in some very unusual activities.  For example, I like to execute algorithms by hand. When I find a pack of cards lying around, I often find myself shuffling them, dealing out about 10-20, and operating a QuickSort on them. Sometimes when I have a stack of old bills and I want to eliminate duplicates while retaining the latest copy for my records, I'll even lay them out in a grid on the floor and perform a bucket sort.

Sorting algorithms are material from Intro to Computer Science 1, but I'm going to give a very condensed overview of the topic as background material to what I'm going to go over in a future post. If you're already rock solid on sorting algorithms, I suggest you skip or skim this one, and I promise I'll get to more practical discussions later.

You'll remember that in the last post on Big O, I explained that a "dumb dictionary search" (just viewing each word one at a time) requires O(n) time, while a more efficient search (which is also known as a "binary search") requires only O(log n) time, which is a lot shorter. But the binary search only works if the words are in some kind order already. If they're all scrambled up -- if "xylophone" comes before "cereal" comes before "pheasant" -- then you have no choice but to execute a dumb search. There's no other way to find your word besides looking at every entry to make sure you didn't miss any.

Therefore, it's often helpful to sort a list of things (such as dictionary words). Of course, sorting a dictionary might take longer than actually searching it. But if you have to search the dictionary multiple times, it's worth it. You eat the cost of sorting only once, but you get to do binary searches as many times as you want after that.

Suppose we take a pack of cards and deal out "n" cards at random. Let's make this quick and pick 5. I'll imagine they came out like this:

• 5, A, 7, K, 3
  

How long will it take to put these cards in the correct order? Well, naturally it can't take less than O(n) time. It's easy to see why. Suppose you had a magic function which automatically skimmed the entire list in no time at all to find the smallest number remaining. Then you could scan these cards and find the Ace first, and put it in the first spot. Then you find the 3, and put it in the second spot. And so on. Then the sequence of events would look like this:

• A, 5, 7, K, 3 (we put the ace in the first spot, but we needed to move the 5 out of the way, so we just swap their positions)
  
• A, 3, 7, K, 5 (3 swapped with 5)
  
• A, 3, 5, K, 7
  
• A, 3, 5, 7, K (sorted!) 
  

This is the most efficient sort possible, but even with our magic function you still have to move each card to the correct location. There are n cards, so it takes n moves. So no matter what happens, we can't do better than O(n). (Technically, it took "n-1" moves to finish, because once the first four cards are sorted, the king MUST be in the right place. There's nothing to swap with. But remember how I said before that constant multipliers don't matter? Subtracting a 1 definitely doesn't matter. In fact, we ignore any constants that are added to or subtracted from the outcome. Order of magnitude is all that counts.)

Unfortunately, we don't have a magic function that takes no time to find the Ace, so we actually have to read the cards in order to find it. How do we do this? Well, we could read the entire list manually, finding the Ace by inspecting every card. This is a technique known as a "selection sort," for the obvious reason that we are looking through the unsorted list to select the smallest number. Like in the dumb dictionary search, that would take O(n) reads to accomplish (technically n/2 on average, but constant multipliers don't matter).

But it's worse than that. Because we have to move n cards, AND we have to read n cards each time we move one. So we do n*n things, which means that this sort is O(n²).

Terrible. Remember, our dictionary had 170,000 words. You square that, and you're doing almost thirty billion operations. There must be a better way.

There is, and one example is QuickSort. QuickSort is a recursive algorithm that is a little bit tedious to explain in a blog post, but it's so successful that it is implemented as a standard feature of many languages. If you type "sort @mylist" in Perl, you are instructing Perl to perform a QuickSort in most cases. If you have some time to kill, I recommend that you look up QuickSort on Wikipedia, lay out some cards, and try to figure out how it works. It's kind of cool.

QuickSort usually requires a time of O(n*log n), and you can't do much better than that. Well, there are some tricks you can use to speed it up if you know exactly what sort of data you're dealing with, even getting pretty close to O(n) in some cases. But for the most part, you're stuck with n*log n. And this makes sense: In the dictionary example we discovered that you can find a word in O(log n) time, and it takes O(n) time to move all the numbers, so in the best case we are going to find a number as quick as possible and then move it.

If you sort a 170,000 word dictionary in O(n*log n) time, how long will it take?  Log 170,000 is about 5, and multiplied by 170,000 itself is about 900,000.  That's not fast, but it's nowhere near as bad as 30 billion.

This is the last purely academic post I'm going to write about Big O notation. By now, I'm sure some readers are asking "What's with all this theory? Am I ever going to use this professionally?"  My answer is: "You might.  For one thing, you can use it to show off in job interviews."  Next time I post about Big O, I'll explain how.

Y2K supplemental

I was looking for a good article that explained Y2K from all angles -- how the problem arose, and an why it ultimately wasn't as serious as people thought.  I couldn't find it before posting, but I like this 1999 article by Tom Christiansen, a major contributor to the Perl programming language.  Not only is Tom an excellent writer, but he accurately dismissed Y2K concerns as overblown before it hit.  You gotta respect a guy with that kind of clear thinking, as well as the courage to voice an unpopular opinion.

A retrospective on the terrifying millenium bug

It's December 31, 1999.  I've got some neighbors over at my house watching movies, and we're all waiting for the rollover.  One of them asks me what time it is.  I check my watch.  "11:58," I say.  "I guess it's time for the world to end.  Want to go outside and watch the fireworks?"  Everybody agrees.

We go outside, and there are fireworks, all right.  My neighborhood is full of people who love fireworks, and they never fail to put on a good show twice a year, on New Year's Eve and Independent Day.

Glancing up, I wryly remark: "The street lights are still on.  Maybe it has to be Pacific Time."

It's the end of the world as we know it

For those of you who are too young to remember or who didn't pay attention to the news from about 1997 onward, January 1, 2000 was the day that civilization as we know it was supposed to collapse.  You see, many computer programs at that time stored information about dates as two digits numbers, which would confuse many computer systems at rollover.  A year of "00" could just as easily mean "1900" as "2000."

Therefore, it was theoretically possible that numerous programs would break in a spectacular fashion, causing bills due in 2000 to be flagged as 100 years overdue.  With interest.  People spent several of the preceding years gloomily talking about how all the computers of the world were completely interconnected, and therefore any systems that did not address this problem might somehow corrupt all the other systems they were connected to.  The Simpsons even devoted a hilarious segment of their annual Halloween special to Y2K in 1999.

Here's what one high profile Y2K alarmist, Gary North, had to say about Y2K (emphasis added):

Who knows where it will start? Only one thing seems certain: it WILL start. And when it does, every market institution and every government will suffer enormous setbacks.  ...

Banking is the obvious domino. Here's another: shipping. What happens to cities if gasoline is unavailable to truckers? If the computers that control train schedules break down? If rail freight cars cannot be located by defective computers? Think about your supermarket's shelves.

What happens to production when "just in time production" becomes "bottleneck production"?

Here's another: farming. Modern commercial farming is tied to hybrid seeds. The plants produced by hybrid seeds produce seeds that will not produce healthy plants if planted. Every year, almost every large farm on earth must re-order another batch of hybrid seeds. If, for any reason, the seed companies fail, or the banks fail, farmers will not be able to plant anything. This will lead to a famine. Let's not hedge our words: FAMINE. There is no way today to get enough non-hybrid seeds into production in order to avoid this problem. If this is one of the dominoes, the result will be widespread starvation.

Hey, everyone!  Remember that one time when the banks failed, governments collapsed, truckers were immobilized, people everywhere were starving, and civilization as we know it ended?  Good times, good times.

In the immortal words of John Cleese, "I got better..."

Disclosure: Gary North was and is an extremely weird dude.  He's a dominionist -- a very special strain of religious zealot who believes that Democracy should be eliminated in favor of a Biblical variety of sharia law.  Complete with public stonings.  North has made a career out of predicting the end of the world at regular intervals, and in the late 90's he just happened to get more traction than usual.

Even so, panic over Y2K was widespread.  I was teaching programming classes at that time, and the course requirements forced me to give students an essay and presentation assignment.  Y2K was one of the possible topics I assigned.  Three or four students chose to write about it, and every single one of their papers unambiguously predicted doom.  Sometime in January 2000, I wrote a mass email to all the former students whose addresses I had, joking "Everyone who wrote about Y2K last year will now retroactively fail the class."

Funnily enough, I personally fixed a Y2K bug.  I was working at the time for Bike.com, one of those multitudes of "dot com" companies that was ultimately doomed to fail, but hadn't gotten the memo yet.  I wasn't a full-time employee; I worked for Compuware, a development shop that farmed me and many other mercenaries out to various little companies for a limited time.  As such, I had a grand view of many such companies during the infamous tech industry crash, but I didn't go down with any of those ships -- at least not until Compuware ran out of work for me and then folded their Austin branch entirely.

Anyway, January 1 fell on a Saturday, so I didn't get back to work until the third.  "We have a problem," my supervisor told me.  "Some of the dates in the bike sales page say that they went online in the year 19100."

I hunted through the code for the offending page, and quickly figured out what was going on.  The code was written in Perl.  Dates in that language represent the year as an integer counting up from 1900.  So the year "1998" is represented as "98," and so on.  Some bright developer who came before me had decided that the proper way to write the full year was "19 . $year".  The period is a concatenate operator, so this bit of code translates to "write the number 19 and then write the year."  Obviously, when the year became "100" the long text representation became 19 followed by 100, or 19100.

That was easy to fix.  I replaced the period with two zeroes and a plus sign, making it display "1900 + $year", because 1900 + 100 = 2000.  I searched all the code for variations of the string "19 ." and performed the same trick everywhere.  The whole operation took less than 20 minutes.  Then I went to my supervisor and announced "Your Y2K problems are all fixed.  That will be ten million dollars.  In tens and twenties, please."

...And I feel fine

If there's a lesson to be drawn here, my take is that software systems are way more resilient than we give them credit for.  People tend to have a certain degree of unreasoning superstition about computer programs.  They are these mysterious and terrifying black boxes that are supposed to serve us, but occasionally fail in inscrutable ways for their own malicious reasons.

Minor tangent: Many people I talk to seem genuinely fearful that the scenario in Terminator or The Matrix really will play out someday; we'll wake up and discover that SkyNet has become intelligent, and also mad as hell at the human race, not to mention being a super-genius planner that can outsmart everyone on Earth.  I always have to point out to these people that it took human beings two billion years of evolution to become as smart as they are.  Even with the benefit of all that complex software in their brains, it takes every human child some eighteen years to explore the world, form up connections and memories, and become a fully functioning adult.

I kind of think we'll notice robots becoming self-aware pretty far in advance, and it will probably be on purpose.  Plus, there's no reason to assume that the intelligent robots will naturally turn on their creators, just as we don't assume that every child will eventually desire to kill his parents.  There are some outliers who become sociopaths and go on a mass murder spree, but most kids do actually grow up to be non-maniacs.

For the time being, all our efforts at what we laughably call "Artificial Intelligence" still result in programs that are fairly dumb, and extremely narrow in their scope.  Computers actually do what we tell them to do.  We programmers frequently tell computers to do the wrong things, in the wrong ways, or fail to be sufficiently precise.  But robust systems like banking are generally written in such a way as to be extremely modular, so that failures are local problems that don't destroy all the data, or accidentally transfer millions of dollars into your bank account.  (Sorry, fans of Office Space... it's really not that easy to rip off a bank.  They wouldn't stay in business very long if it were.)

Certainly there are cases where a misapplication of computers can do something so dangerous that it jeopardizes national security.  Here's an interesting recent story of government secrets being sent to Iran via BitTorrent.  But as you might expect, the computer itself is not the villain: like deliberately written viruses, stealing files in this manner is a deliberately designed spy technique that is executed to take advantage of existing software.  It takes an intelligent agent to make computers do something harmful in a creative way.

So I remain highly skeptical of a catastrophic bug that will magically, accidentally, without deliberate effort, somehow cause a simultaneous collapse of millions of computer system worldwide.  In the Simpsons episode I mentioned, all the computers in the world are fixed, but because Homer fails to fix his own particular system, that one failure somehow "infects" the rest of the internet.  Comedy!

But the truth is a lot more mundane: individual programs screw up all the time.  The better ones are written in a way to isolate and localize the errors.  The worse ones either fix their problems or go obsolete.

Many companies were destroyed in the aftermath of 2000, but it wasn't the fault of the milennium bug; it was just another example of human error.  In this case, it was poor business planning.  Go to bike.com now if you want.  There's no impressive web site with a massive database of bicycle sales.  Instead, it's a small shell of a site that hosts a few third-party ads.  This isn't the company I worked for; those guys probably went bankrupt long ago because very few people actually want to buy bikes on the internet.  The domain has been taken over by a company whose business strategy is barely more ambitious than cybersquatting web sites.

So worry about failures due to ordinary hubris, sure.  But don't worry about a massive robot uprising, or a simultaneous failure of all the world's software.  And if you want to rip off investors, there's no need to count on obscure computer glitches, just do it the old-fashioned way: lobby to roll back industry regulations, invest in super-risky schemes, and then push your losses on the taxpayers on the grounds that your company is too big to fail.

Speed up your programs with Big O (part 1)

Part of what inspired me to do this blog was that I found myself explaining "Big O Notation" to two coworkers this week. My coworkers are smart people, but I was a little surprised to find that some aspects of computer science aren't common knowledge.

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.

Get Smart

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:

1. 170,000
2. 85,000
3. 42,500
4. 21,250
5. 10,625
6. 5,312
7. 2,656
8. 1,328
9. 664
10. 332
    
11. 166
12. 83
13. 41
14. 20
15. 10
16. 5
17. 2
18. 1

18 Words we looked at. Instead of 85,000. Much better, right?

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
2¹⁸ > 170,000
(17 wouldn't be enough. Check.) If you fiddle with that equation, you'll find that
18 > log₂ 170,000

So, to speak more generally, the smart dictionary search is O(log₂ 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(log₂ n).  But the "2" subscript in "log₂" 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(n²).  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(n²) 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.

I dream of recursion

This is a true story. I have told it to my programming classes every time I introduced the topic of recursion.

When I was a little kid, there was a toy that I desperately wanted. We'll just gloss over what it was because it's not in any way important to the story. So one night --

All right, all right, stop whining. I'll tell you. It was... a Ronald McDonald doll. That whistled. Yes, it had a little plastic whistle, and if you squeezed it then it would whistle. As seen on TV. Why in the world would I want that? I have no idea. I just remember that it seemed very important at the time.

So I wanted this Ronald McDonald doll. Very much. But I knew that my dad, who has always been a practical minded guy, would find this toy, well, stupid. So I didn't have the courage to ask him for it. But then to my surprise, one evening I came home from school, and my dad said, "Russell, today we're going to Toys R Us to pick up that Ronald McDonald you've been wanting."

Needless to say, I was ecstatic. We got in the car, drove to the store at the mall, picked up that toy, brought it home, and...

...Then I woke up.

As bitterly disappointed as I was to learn that it was all just a dream, I was filled with a new confidence. I just knew that my dad was going to buy that toy for me, because the dream had so foretold. So I went into the breakfast nook, where I found my dad waiting. I asked him if he would get me the Ronald McDonald doll that whistles, and he says "Surprise! I already got it for you! There it is!"

...And I woke up.

But after having been through this experience twice, I was more certain than ever that I would be getting my toy. Sure enough, I went to find my dad, asking "Did you REALLY get me that toy?" He said "I sure did! Look!" I actually got to play with the thing for a while, and then -- all together now,

...I woke up.

I think you get the idea. It feels like the sequence repeated itself about ten times or so, although of course there's no way to tell. Each time the details of the nested dream were a little different, but the end result was always the same: I was confident that I'd get the toy, I did get the toy, and I woke up. And each time I woke up, the world seemed a little more "real" to me than the one in the previous dream.

Except for the last time. When I really woke up, I knew I was really awake. I didn't even need to bother asking my dad about it in the real world. I know reality.

I never did get that toy. That probably explains exactly why I am the bitter cynic I am today.

The tricky part about this story is still how to translate it from amusing anecdote to actual concept of computer science. If this were true recursion, I would probably remember going to sleep ten times in a row at the beginning, then getting the toy for the first time, and so on. Instead, I started in mid-dream. But nobody ever remembers going to sleep anyway, so we can assume that happened in there somewhere. So if I had to pseudo-code this story, it would look like this:

class YoungRussell {
    void sleep () {
        lieDown(bed);
        fallAsleep();
        dream();

        // perform operations associated with
        // waking up here
    }

    void dream () {
        if(someTerminatingCondition() == false) {
            // no actions before falling asleep
            // again in the dream
            sleep();
        }
        StupidToy ronald = new StupidToy();
        obtain(ronald);
        playWith(ronald);
    }

    // ...
    // auxiliary methods here
}

Wait... where's the actual waking up routine, you ask? Well, you don't need one. Reaching the end of the "dream" routine automatically drops you back into the conclusion of the "sleep" routine, and when "sleep" ends, you just wake up.

I have always found this the hardest thing for people to understand about recursion.