a couple thoughts:
1) approximate randomized algorithms are your friend, especially when we talk about things like (RAN|MAP|MLE|M)SAC in model fitting. for some classes of problems, random approximate algorithms are the *only* attack that we have that are feasible in terms of time/space complexity.
2) your analysis fails to account for the hidden leading constant (otherwise there's no reason to consider quicksort when you have heapsort) and what happens when N gets to be large enough. the fact is that for big enough N or big enough S, the lower order algorithms will start to become dramatically faster, even if repeated applications are necessary to cross-validate results.
3) unless you're using arbitrary precision math, all of these algorithms are approximate anyway and great care must be taken to understand how these systems can be (pre)conditioned to minimize the compounded effects of fixed precision arightmetic.