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?

2 Comments »

  1. 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

  2. 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

Leave a comment

Warning: When entering a long comment, please ensure that you make copy of your text prior to submitting it. If the server should fail or if you hit a bug, you might lose your work. I am not responsible for your lost effort.

To spammers: I carefully review every single post and make sure that spam gets deleted. You are wasting your time if you are manually entering spam using this form. Read my terms of use to see what I consider to be abusive.

Example: duo plus septem is '9'. The numbers are expressed in latin numerals but you should give your answers using ordinary digits.

 

« « Previous: The insane world of academic publishing
Next: My blog got hacked » »

« Blog's main page

Powered by WordPress

© 2004-2012, (lemire at gmail dot com). This work is licensed under a Creative Commons License.