News for hackers. Stuff that matters.
Re:Potato paradox by hofstee on Thursday July 16, 2015 @05:57PM (#9900129)
There is a sorting network called AKS which has O(log(n)) depth. Batcher's Odd-Even Mergesort has a depth of O(log^2(n)). Which is better?

In all cases where you can fit n in the total memory capacity of the earth, Batcher's network is vastly superior. Constants matter a whole lot more than you might think.

I'm not arguing against revising algorithms to look for better complexity classes, but if you rewrite your algorithm in a smaller complexity class you had better be sure that your constants are of reasonable size.

Re:Potato paradox by calinet6 on Friday July 17, 2015 @09:12AM (#9902533)
For sure. But that's a far more nuanced argument than "twice as fast." :)