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.
Related Articles
5 users responded in this post
Maybe I’m being an idiot, but if it takes 1 millionth of a second to process one pixel, surely it takes one second to process a one megapixel image and three seconds to process a three megapixel image? That’s definitely linear.
I am honored that you took the time to visit my little blog Ben :). Thank you.
With regards to the math, let me see if I can justify it correctly:
1 Mega pixel = 1024 Kilo pixel = 1048576 pixel. This is our N.
N * N = N^2 = 1099511627776 operation using an O(N^2) algorithm on 1048576 pixel.
With 1 microsecond for each pixel operation, we need 1099511.627776 Second = 18325.193796267 Minute = 305.419896604 Hour = 12.7258 Day.
As for the linearity, Check f(x) = x^2 in this image http://en.wikipedia.org/wiki/Image:Function_ax%5E2.jpg . Without using the image, f(1) = 1, f(2) = 4, f(3) = 9. If the function was linear, there would have been a constant increase in the result of the function as x in f(x) increases. As x increases by 1 each time, the increases in f(x) are 3 then 5.
As I’m still rediscovering the joy of math, please tell me if any of the above seems illogical.
I think that the problem is in the phrasing of the example problem. Saying that it takes 1 millionth of a second to process one pixel implies a pixel-processing algorithm that is O(1), ie constant time. If you then state the size of the image in linear terms (1, 2, 3 megapixel) then you are executing an O(1) algorithm n times, giving you an O(n) algorithm to process the entire image.
If, on the other hand, the algorithm for each pixel sampled the value of every other pixel in the image then that algorithm would be O(n), and running it n times would indeed result in an O(n²) algorithm to process the entire image.
PS 1 megapixel in digital cameras is 1 million pixels, not 1024*1024 pixels. :)
Oh, I see (I thought something was wrong when I started writing that simple math. I thought you were testing me or something :P).
Hmm, yeah, mostly I think he was talking about the 2nd case.
Thanks for a lot the explanation! :)
(Doh! *forehead smack*, 1024 is for bytes only)
Okay, this comment has nothing to do with your post!
How come you didn’t link me to your blog!!! it looks great! nice new design :)
Leave A Reply