Re: Using Java Classes to Sort a Small Array Quickly
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