During high school and for a time in college, I hated job interviews. Looking back, I think it’s safe to say that fear, rather than pure hatred, caused me to turn an abhorrent eye toward these things. I just couldn’t stand the idea of getting dressed up just to have someone prick and prod my brain like cattle. Thankfully, as I have become more experienced professionally and I have grown more confident about my abilities, I have come to really enjoy the process.

So what does this have to do with Signor Pisano’s famous number sequence? Well, during a job interview some years back, I was tasked to write a function in ActionScript to calculate the Fibonacci number for a given order n in the sequence. When about twenty minutes later I still couldn’t solve the problem, my chances for further consideration were doomed.

After that nightmare, I was determined to figure out a solution on my own. Here’s the solution I came up with in Java, ignoring input verification:

toggle line numbers

It turns out that this is a standard solution to this little problem. So now I could go on my way confident that no interviewer will ever get me on that one again. I’ve even asked the same question a few times to potential candidates I’ve interviewed.

Because my current job gives me the flexibility to do so, this year I started taking a few CS classes at the University of Texas at Austin. I enjoy it very much, and my programming knowledge and skill have only improved as a result. Today was my first day of classes for the fall semester. This time around I’m auditing a one-hour course on Ruby and and I’m enrolled in a second-year course on data structures taught by Professor Gordon S. Novak where we’ll be tackling Lisp as well as a few other languages besides Java.

I’m already thinking that I like this guy when he begins a short intro on Lisp with an example function to calculate a Fibonacci number:

toggle line numbers

At this point I’m thinking, “I rock!”. He then pulls up an alternative solution, which I immediately proceed to ignore lest I spoil this moment of self-appreciation:

toggle line numbers

Now on his laptop, he nonchalantly begins to compare the two solutions:

toggle line numbers

So far, so good.

toggle line numbers

So he keeps increasing slightly and then finally jumps to 200:

toggle line numbers

“What’s happening here?” he asks us. A few people call out that it’s still calculating.

“Do you think if we wait a few minutes, we’ll get the answer?” Silence.

“Do you think it’ll finish by the end of the hour? The day? This year?”

He then takes a moment to explain how scientists believe that the earth has about 6 billion years or so left until it gets gobbled up by an expanding sun, “at which point this program will have yet to calculate the solution.”

Gasp! All of my dreams of becoming the next Bill Gates dashed in an instant! The problem with little fib1 is that for every call to itself, two additional calls are being made. Thus we have an illustration such as this:

n           fib1
|          /    \
|       fib1     fib1
|      /    \   /    \
|   fib1  fib1 fib1  fib1
V   /  \  /  \ /  \  /  \

So as n increases linearly, the number of calls to itself increases exponentially. What does this give us in terms of Big O? The dreaded O(2ⁿ).

Therein is a simple, yet powerful example of the importance of understanding algorithm analysis. While this example may not be immediately applicable to my job, dealing with performance issues is at the heart of what a web developer does, so I’m happy for the lesson.