NNTP-Posting-Date: Thu, 01 Sep 2011 03:20:48 -0500 Date: Thu, 01 Sep 2011 09:20:48 +0100 From: bugbear User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.1.19) Gecko/20110429 Fedora/2.0.14-1.fc13 SeaMonkey/2.0.14 MIME-Version: 1.0 Newsgroups: comp.lang.java.programmer Subject: Re: Using Java Classes to Sort a Small Array Quickly References: <86c4a53b-1ca1-48a8-b954-c01bd449278a@s35g2000prm.googlegroups.com> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Message-ID: <4K-dnfLlx9H93cLTnZ2dnUVZ8n2dnZ2d@brightview.co.uk> Lines: 21 X-Usenet-Provider: http://www.giganews.com X-Trace: sv3-oByqqG3ZcWbOpzX7f4DlNje/dehYHSNtlrME+NbbOgiSlF/7ZN/NLXWcaJtji8OYuKbMjsHqGe5fWTK!7O/hN9CY0W7WkHJf75XACaZ+9k0eurhFDFbItfYICR7sdVXGFKCFXbQMvUJAw6bmQuUYydbz0Bgr!1CA2a2uoTMrKzUgEw6jdkMvODA== X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 1853 Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.stben.net!border3.nntp.ams.giganews.com!Xl.tags.giganews.com!border1.nntp.ams.giganews.com!nntp.giganews.com!local2.nntp.ams.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:7514 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 forget his value of 'N'. BugBear