21 Feb
2012
21 Feb
'12
8:08 a.m.
* Victor Miller <victorsmiller@gmail.com> [Feb 21. 2012 15:25]:
You should read the hilarious paper "Pessimal Algorithms and Simplexity Analysis" by Andrei Broder and Jorge Stolfi http://www.cs.uiuc.edu/class/fa05/cs473ug/resources/pessimal-algorithms.pdf. They have a strong definition of pessimal algorithm -- one that does badly even in the best case. So you have to work hard to avoid accidentally finding the right answer too soon. Their triumph is "slow sort". They get it from the standard quicksort program by only changing two lines. It is exponential in the best case (i.e. it takes exponential time even when the input is already sorted).
Victor
Lovely! Thanks for the pointer, jj