I admit it, I used to consider computing the Big-O of algorithms you write is ridiculously useless. “We have these powerful machines nowadays!” and boy was I wrong …. In http://leepoint.net/notes-java/algorithms/big-oh/bigoh.html and under Why Size Matters
Does anyone really have that much data?
It’s quite common. For example, it’s hard to find a digital camera that that has fewer than a million pixels (1 mega-pixel). These images are processed and displayed on the screen. The algorithms that do this had better not be O(N2)! If it took one microsecond (1 millionth of a second) to process each pixel, an O(N2) algorithm would take more than a week to finish processing a 1 megapixel image, and more than three months to process a 3 megapixel image (note the rate of increase is definitely not linear).
Another example is sound. CD audio samples are 16 bits, sampled 44,100 times per second for each of two channels. A typical 3 minute song consists of about 8 million data points. You had better choose the write algorithm to process this data.
A dictionary I’ve used for text analysis has about 125,000 entries. There’s a big difference between a linear O(N), binary O(log N), or hash O(1) search.
HOWEY! a week for 1 megapixel image using an O(N2) algorithm!! …. Ok, sure, on a desktop application where the data are usually small and the processor is fast, it doesn’t matter much. But for heavily visited web sites (huge data) or for small devices (slow processor) it makes a world of difference. I better watch for this in my current projects, one’s expect heavy traffic (huge data) and the other is a mix of medium/big data and slow-ish server. Better go revise the code.
