Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail
From: markspace <-@.>
Newsgroups: comp.lang.java.programmer
Subject: Re: Using Java Classes to Sort a Small Array Quickly
Date: Mon, 12 Sep 2011 19:49:02 -0700
Organization: A noiseless patient Spider
Lines: 35
Message-ID: <j4mgb0$h1c$1@dont-email.me>
References: <86c4a53b-1ca1-48a8-b954-c01bd449278a@s35g2000prm.googlegroups.com> <j3mupc$d5m$1@dont-email.me> <MPG.28d742f5c91d21e9896b8@202.177.16.121> <j4jala$dkh$1@dont-email.me> <MPG.28d76557830521d69896ba@202.177.16.121> <fuhs67lrl26ubtv16brfg56c4kueldb28k@4ax.com> <4e6e8f47$0$308$14726298@news.sunsite.dk> <j4mblo$p46$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 13 Sep 2011 02:49:04 +0000 (UTC)
Injection-Info: mx04.eternal-september.org; posting-host="XjIWM99mD7Ijfdu600oVPA"; logging-data="17452"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+/f49Xc6V8VDtLIxhS3CpeYRx0MnaoFjU="
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:6.0.2) Gecko/20110902 Thunderbird/6.0.2
In-Reply-To: <j4mblo$p46$1@dont-email.me>
Cancel-Lock: sha1:+OIw3LrsWViaZCz/QQeLagN/gOU=
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:7945

> On 9/12/2011 7:01 PM, Arne Vajhøj wrote:
>> No - big O for algorithms is usual average case not worst case.


I'm pretty sure that is not correct.  Quoting Wikipedia:

"Informally, especially in computer science, the Big O notation often is 
permitted to be somewhat abused to describe an asymptotic tight bound 
where using Big Theta Θ notation might be more factually appropriate in 
a given context."

That is to say, Big O is the upper bound.  Big Theta is the average case 
or the expected case.

<http://en.wikipedia.org/wiki/Big_O_notation>


>> I am sure you can find plenty of quotes for quicksort being
>> O(nlogn) and not O(n^2).

On 9/12/2011 6:29 PM, Eric Sosman wrote:
> Quicksort takes O(n*log n) *average* time, O(n*n) *worst case*
> time.


Both of these are also incorrect, I think.  The sort time for quick sort 
is O(n log n) for RANDOM data.  This can be proven.  The worst case is 
O(n^2) and that's for already sorted data, a not unreasonable input.  So 
the n log n number for quicksort is for a particular arrangement of 
data, not the actual upper bound.

The random data argument is a bit like the spaghetti sort.  It works 
well for certain types of input, like spaghetti, not so well with other 
types of data.