quick sort and O(nlgn) worst case bound
in [General Programming]
|
From: Richard Heathfield on 29 Jan 2010 11:10 Stephen Howe wrote: >> It also happens to be the paper under discussion. >> And as Jon Harrop has stated, >> the paper does not apply to all quicksorts. > > Yes does the paper apply to quicksorts where the pivot selection is O(1) ? > If the pivot selection is O(N) you can gurantee to get the median every time. > > I think I am saying that all quicksorts will have at least 1 worst case if the pivot selection is O(1) Um, did you mean what you just said? Surely *all* algorithms have at least 1 worst case? -- Richard Heathfield <http://www.cpax.org.uk> Email: -http://www. +rjh@ "Usenet is a strange place" - dmr 29 July 1999 Sig line vacant - apply within
From: Stephen Howe on 29 Jan 2010 11:35 >> I think I am saying that all quicksorts will have at least 1 worst case if the pivot selection is O(1) > >Um, did you mean what you just said? Surely *all* algorithms have at >least 1 worst case? All right, rephrasing that: I think I am saying that all quicksorts will have at least 1 worst case that is O(N * log N) if the pivot selection is O(1) Stephen Howe
From: Ben Bacarisse on 29 Jan 2010 13:52 Stephen Howe <sjhoweATdialDOTpipexDOTcom> writes: >>> I think I am saying that all quicksorts will have at least 1 worst case if the pivot selection is O(1) >> >>Um, did you mean what you just said? Surely *all* algorithms have at >>least 1 worst case? > > All right, rephrasing that: > > I think I am saying that all quicksorts will have at least 1 worst > case that is O(N * log N) if the pivot selection is O(1) That needs re-phrasing as well. First off, did you mean O(N * log N) there? I suspect you want to say that with O(1) pivot selection all quicksorts are Theta(n * n). (Theta is both an upper and a lower bound so it is more helpful when describing how bad things can be. An O(n * log n) algorithm is also O(n * n) and O(n * n * n) etc.) The other problem is that there is no meaning of big O for a single case. No single bad case can have any effect on the asymptotic behaviour of an algorithm. You probably meant that there is some pattern of cases that uncovers that bad performance. -- Ben.
From: Stephen Howe on 29 Jan 2010 14:57 >> All right, rephrasing that: >> >> I think I am saying that all quicksorts will have at least 1 worst >> case that is O(N * log N) if the pivot selection is O(1) > >That needs re-phrasing as well. Yes, my mistake. 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). >First off, did you mean O(N * log N) there? I suspect you want to say >that with O(1) pivot selection all quicksorts are Theta(n * n). Yes. I have just been thinking about the existence of a lower bound. But it is only applied for the distributions that blow up. Otherwise it is not a lower bound. >The other problem is that there is no meaning of big O for a single >case. No single bad case can have any effect on the asymptotic >behaviour of an algorithm. You probably meant that there is some >pattern of cases that uncovers that bad performance. Yes. I am saying there is a at least 1 distribution as N => infinity if pivot selection is O(1) Stephen Howe
From: Ben Bacarisse on 29 Jan 2010 16:37
Stephen Howe <sjhoweATdialDOTpipexDOTcom> writes: >>> All right, rephrasing that: >>> >>> I think I am saying that all quicksorts will have at least 1 worst >>> case that is O(N * log N) if the pivot selection is O(1) >> >>That needs re-phrasing as well. > > Yes, my mistake. 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). Sorry to bang on about it, but O(f) is an upper bound. Let's assume that the worst input case provokes quicksort into using no more than n*log(n) comparisons. It would *still* be correct to describe it as O(n*n) because very f in O(n*log(n)) is also in O(n*n). >>First off, did you mean O(N * log N) there? I suspect you want to say >>that with O(1) pivot selection all quicksorts are Theta(n * n). > > Yes. I have just been thinking about the existence of a lower bound. > But it is only applied for the distributions that blow up. > Otherwise it is not a lower bound. If all you want is to express the lower bound, use Omega instead of Theta. <snip> -- Ben. |