Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder5.news.weretis.net!feeder1.news.weretis.net!news.swapon.de!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail From: Joshua Cranmer Newsgroups: comp.lang.java.programmer Subject: Re: Using Java Classes to Sort a Small Array Quickly Date: Tue, 13 Sep 2011 11:32:43 -0500 Organization: A noiseless patient Spider Lines: 34 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=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Tue, 13 Sep 2011 16:33:19 +0000 (UTC) Injection-Info: mx04.eternal-september.org; posting-host="WpcHJSul77m+zlbR9GVqkA"; logging-data="10099"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19HWZOJGjbi3EWb/5L67izq04vzjxLb/u4=" User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:6.0.2) Gecko/20110902 Thunderbird/6.0.2 In-Reply-To: Cancel-Lock: sha1:aiHIgXCyOzJ5zykBKOKQ/y0dsPo= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:7976 On 9/12/2011 9:49 PM, markspace wrote: > That is to say, Big O is the upper bound. Big Theta is the average case > or the expected case. The first part of that statement I might accept as a simplification, while the second sentence I would definitely not. f(x) = Theta(g(x)) if and only if lim x->inf f(x)/g(x) is neither 0 nor infinity; in other words, f(x) and g(x) have the same asymptotic behavior up to a constant. Big-O really just means that the function will grow no faster than another; in a way, it's a pessimistic bound: you can prove that your function is O(n^3), but it could still be O(n^2) and you can't prove that it is. If a function is Theta(n^3), however, there is no way in hell that it could be O(n^2); you have proven that it is exactly cubic in all cases. You can use any of these for best-case, average-case, or worst-case performance, although using big-O for the best-case performance is somewhat counterintuitive. > 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. There are ways to touch up quicksort to achieve Theta(n lg n) time for sorted data, and the implementation in the JVM does so. -- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth