quick sort and O(nlgn) worst case bound
in [General Programming]
|
From: Ben Bacarisse on 31 Jan 2010 12:28 Jon Harrop <jon(a)ffconsultancy.com> writes: > Ben Bacarisse wrote: >> Jon Harrop <jon(a)ffconsultancy.com> writes: >>> Ben Bacarisse wrote: >>>> I suspect you want to say that with O(1) pivot selection all quicksorts >>>> are Theta(n * n). >>> >>> Probably not given that sorting a sequence of identical values should be >>> O(n) even with O(1) pivot selection. >> >> Hmm... not sure if I get your point. > > I'd say it was Omega(1) and O(n^2). > >> The function being described is, presumably, the greatest number of >> comparisons used taken over all inputs of size n. > > Why the greatest? From the context. I was trying to re-phrase what someone else seemed to be trying to say. He wanted to state how bad a class of sort can get using O(f) notation which, of course, does not work and I was suggesting using a lower bound on the worst case for each size. The original statement talked about the "worst case" which I took to be the maximum no. of comparisons. In a sub-thread all about clarity, it was probably not clear enough. The simplest way to say that some function of an algorithm is worse than O(f) is simple to state that it is not O(f), but the poster wanted to say something stringer than that. <snip> -- Ben.
From: pete on 11 Feb 2010 12:23
Stephen Howe wrote: > I think I am saying that for all quicksort algorithm where the pivot selection is O(1), > there exists a family of distributions > as N tends to infinity such that sorting is O(N *N). I also think that there is. And that was the point of the paper which had been mentioned. -- pete |