quick sort and O(nlgn) worst case bound
in [General Programming]
|
From: Stephen Howe on 29 Jan 2010 18:16 >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). But you can also say f is also in O(n * n * n) and every f is in O(n * n * n * n) and so on. All very true but not useful. You want tight asymptotic upper bounds that correctly describes the behaviour for all cases. Cheers Stephen Howe
From: Ben Bacarisse on 29 Jan 2010 19:46 Stephen Howe <sjhoweATdialDOTpipexDOTcom> writes: >>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). > > But you can also say f is also in O(n * n * n) and every f is in O(n > * n * n * n) and so on. All very true but not useful. You want > tight asymptotic upper bounds that correctly describes the behaviour > for all cases. This is pretty much what I've been saying, but you've managed to make it sounds as if *I* was pushing the use of these unhelpful upper bounds! -- Ben.
From: Jon Harrop on 30 Jan 2010 10:40 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. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: Ben Bacarisse on 30 Jan 2010 17:19 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. The function being described is, presumably, the greatest number of comparisons used taken over all inputs of size n. The existence of simple-to-sort cases does not stop this function being in Theta(n*n). -- Ben.
From: Jon Harrop on 31 Jan 2010 02:04
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? > The existence of simple-to-sort cases does not stop this function being in > Theta(n*n). Unless all cases are simple-to-sort. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u |