------- Comment #7 from sjhowe at dial dot pipex dot com 2008-04-28 20:17 ------- Roger
I agree with your analysis. I am slightly crestfallen as I was suspicious that Barriato, Hofri etc's paper never mentioned "worst case" only "approximate case". And I have now seen BFPRT73 paper where it mentions for the number of columns (c) "Note, however, that we must have c >= 5 for PICK to run in linear time". So yes, median-of median of 5 seems best you can do for "worst case". The only point in shifting to a different algorithm for the worse case is if (i) It is cheaper in terms of total comparisons, swaps, assignments etc (ii) It is still linear in N in the worse case Cheers Stephen Howe -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968
