Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail From: Eric Sosman Newsgroups: comp.lang.java.programmer Subject: Re: Using Java Classes to Sort a Small Array Quickly Date: Mon, 12 Sep 2011 21:29:23 -0400 Organization: A noiseless patient Spider Lines: 36 Message-ID: References: <86c4a53b-1ca1-48a8-b954-c01bd449278a@s35g2000prm.googlegroups.com> <4e6e8f47$0$308$14726298@news.sunsite.dk> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Tue, 13 Sep 2011 01:29:28 +0000 (UTC) Injection-Info: mx04.eternal-september.org; posting-host="f8igmItKsWs6nM5YanFxAA"; logging-data="25734"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18AiDEvKCzANT+eHpJX8SJl" User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:6.0.2) Gecko/20110902 Thunderbird/6.0.2 In-Reply-To: <4e6e8f47$0$308$14726298@news.sunsite.dk> Cancel-Lock: sha1:j9ktIt3vG3JHYAWuOzgc5CbCDAs= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:7943 On 9/12/2011 7:01 PM, Arne Vajhøj wrote: > On 9/12/2011 1:57 PM, Gene Wirchenko wrote: >> On Mon, 12 Sep 2011 01:40:50 +0200, Wanja Gayk >> wrote: >>> In article, esosman@ieee-dot-org.invalid >>> says... >>> >>>> Very nice! Would you care to try this approach on a shorter >>>> input array, like >>>> >>>> data = new int[] { Integer.MAX_VALUE }; >>>> >>>> This case should be quite simple, since the array is already sorted. >>>> Let us know how you make out, will you? >>> >>> I didn't say it works for any array out there, did I? >> >> You did. Claiming an algorithm is O(n) means claiming that that >> is the upper bound. > > No - big O for algorithms is usual average case not worst case. Big O is for whatever quantity it is measuring. > I am sure you can find plenty of quotes for quicksort being > O(nlogn) and not O(n^2). Quicksort takes O(n*log n) *average* time, O(n*n) *worst case* time. Neither of the Big O's is in any way "preferable" to the other: They are describing different aspects of the algorithm. There is no reason to *expect* "average time" and "worst case time" and "time off for good behavior" to have similar Big-O expressions. -- Eric Sosman esosman@ieee-dot-org.invalid