Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: binary search with arbitrary or random split
Posted:
Aug 7, 2012 8:22 PM


[Followupsto set since I don't think sci.math.numanalysis is topical anymore.]
Ralph Hartley <hartley@aic.nrl.navy.mil> writes:
> On 07/24/2012 06:02 PM, Ben Bacarisse wrote: >> What's going on here? If there were any down side at to using n/2 I can >> see why one might consider alternatives  even random ones (some people >> do for quicksort, partitioning for example)  but since n/2 is simple, >> easy to calculate and optimal you can't be proposing an alternative. > > For searching a sorted list, I agree it doesn't make much sense, but > consider sorting. > > Quicksort is a simple algorithm, and is close to O(n log(n)) for most > inputs, but you can't use it when the input is chosen by an adversary > because in worst case it is O(n^2). > > It is reasonable to use quicksort with each pivot point chosen > randomly from a uniform distribution over the list. Unlike search, > there is no consistently good choice, and any deterministic rule could > be exploited to give O(n^2) cost *every* time.
That's not true. You can pick the median in O(n) time and that means (if you're careful about a few other details) that you can have a deterministic quicksort that is O(n log(n)) in the worst case. It's not really practical, but that's not the point.
> Worst case is *still* O(n^2), but that's ok. What you really care > about is that the average over your random choices is O(n log(n)), > even for the worst possible input.
Depends on who "you" refers to! People interested in complexity theory (this is comp.theory after all) are more likely to be interested in worstcase analysis. This is not to deny the large body of theory on probabilistic analysis  it's just not the majority concern for complexity theorists.
> I think you can actually say something slightly stronger than that, > and show that the probability of very bad cases is small.
Yes, I think so too, but I don't know if there is an agreed measure for "bad cases are sufficiently rare". The one paper cited in this thread, proposed one, but I had trouble getting me head around it.
> It's OK to assume that your random choices follow a known > distribution, you can make them so, but it can be a disaster to assume > that the input array is anything but worse case. > > There are sorting algorithms with better worst case, but they are > often not worth the trouble. > > None of this is *remotely* new.
No, but probabilistic measures of "almost always" O(f) are newer (if not actually new). I'd be interested to hear from anyone who know what recent thinking is about such things.
 Ben.



