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: Thu, 01 Sep 2011 08:06:33 -0400 Organization: A noiseless patient Spider Lines: 30 Message-ID: References: <86c4a53b-1ca1-48a8-b954-c01bd449278a@s35g2000prm.googlegroups.com> <4K-dnfLlx9H93cLTnZ2dnUVZ8n2dnZ2d@brightview.co.uk> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Thu, 1 Sep 2011 12:06:33 +0000 (UTC) Injection-Info: mx04.eternal-september.org; posting-host="f8igmItKsWs6nM5YanFxAA"; logging-data="7212"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19Bi0jadt0shxzBnZFCOrHH" User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:6.0.1) Gecko/20110830 Thunderbird/6.0.1 In-Reply-To: <4K-dnfLlx9H93cLTnZ2dnUVZ8n2dnZ2d@brightview.co.uk> Cancel-Lock: sha1:PDYWcfHuJ4wvwuScIZdbB0SbbXU= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:7524 On 9/1/2011 4:20 AM, bugbear wrote: > Eric Sosman wrote: > >> Besides, you're misusing O. Suppose I offer you two algorithms, >> one whose running time is O(N^2) and the other O(N). Which is faster? >> Before you say "O(N), nitwit," let me show you the actual timing >> formulae: >> >> T1(N) = N * N (nanoseconds) >> T2(N) = N (gigayears) >> >> T1(N) is clearly O(N^2), while T2(N) is O(N). Which do you choose >> for sorting N=12 items? > > Conversely, Jon Bentley in an (evidently...) old book gives > an example (with implementations and timings) > where quicksort on a TRS-80 outperforms > bubble sort on a Cray-1. I think it was in a CACM column; can't remember whether it was part of his "Programming Pearls" series or not. The latter have been collected in book form. > I forget his value of 'N'. So do I. -- Eric Sosman esosman@ieee-dot-org.invalid