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: Gene Wirchenko Newsgroups: comp.lang.java.programmer Subject: Re: Using Java Classes to Sort a Small Array Quickly Date: Wed, 14 Sep 2011 11:00:15 -0700 Organization: A noiseless patient Spider Lines: 29 Message-ID: References: <86c4a53b-1ca1-48a8-b954-c01bd449278a@s35g2000prm.googlegroups.com> <4e6e8f47$0$308$14726298@news.sunsite.dk> <4e700893$0$311$14726298@news.sunsite.dk> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit Injection-Info: mx04.eternal-september.org; posting-host="7Qrvczazr82YckO5XW8Vtw"; logging-data="21148"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+DUbTIT2yN3Nj83hsMoLYy4zirrIeILKY=" X-Newsreader: Forte Agent 4.2/32.1118 Cancel-Lock: sha1:r3XggVq5ECVOMpLHVhx/ltv31cE= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:8026 On Tue, 13 Sep 2011 21:51:13 -0400, Arne Vajhøj wrote: >On 9/12/2011 10:49 PM, markspace wrote: >>> 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. >> >> > >I don't think upper bound in this case means worst case. Well, yes, it is. That is why it is the upper bound. If a worse case were possible, then that limit would not be the upper bound. [snip] Sincerely, Gene Wirchenko