First off, fair warning this is going to be very nerdy but I find it interesting so enjoy!

In high school computer science class I was introduced to the idea of complexity. Complexity is a way to describe how efficient a program is. In other words how much computer memory does the program need and how fast can the program be completed. Complexity is described mathematically using what is called big O notation and is written as a function of time or memory in terms of the input size. For example O(n^2) means that for n number of inputs the time to complete the program increases quadratically. Big O notation is always written as a function of one term with no coefficients. Examples are O(n), O(n^3), O(log n), etc.

Obviously some of these complexities are problematic because as the size of the input increases the complexity increases much faster. For example O(n^3) with an n value of 100,000 has 10^15 operations to perform. If the computer runs through a million operations per second the program wouldn't stop running for almost 32 years! If your computer lasted for that time it would be incredibly obsolete. Clearly no one has time to run a program for this long and 100,000 isn't even that large of an input number (consider that google searches deal with billions of sites).

So this interests me because I recenty wrote an algorithmn that is O(n^3). So am I waiting until I'm 51 to see if I implemented it succesfully? Well no because it turns out there is a big difference between theoretical complexity and complexity in practice. You know how earlier I said big O ignores coefficients and lesser degree terms. Well in theory you can do that but in practice they turn out to be very important. The complexity of what I wrote is in practice a quadratic equation. The coefficients further decrease it and with an input size of 100,000 it turns out it takes less than two hours to run.

The moral of this story for programmers is that just because something seems too complex to implement when it is being planned does not mean it can't be implemented more cheaply. There are often methods of reducing complexity that allow you to do a lot more on the same hardware. Just something to think about the next time you are planning a program.