If you claim high scalability…
I just reviewed a paper where the authors come up with a nice highly scalable algorithm. And it is really scalable too! But to prove just how fast it is, they process 2,000 data points.
This is correct, strictly speaking. Their algorithm runs in O(n) time, so to know how long it would take to process 1000 times more data, just multiply by 1000.
But where is the fun in that?
Montreal, Canada 
Facebook
Friendfeed
LinkedIn
SlideShare
Delicious
Their algorithm runs in O(n) time, so to know how long it would take to process 1000 times more data, just multiply by 1000.
Is that even true? It ignores memory hierarchy effects.
Comment by D. Eppstein — 25/8/2008 @ 15:38
But where is the fun in that?
What do you mean?
Not trusting a “proof” over only 2000 datapoints?
Comment by Kevembuangga — 26/8/2008 @ 2:22