Re: Hoare's gripes about Ada (should be so what)

[cis.ohio-state.edu!magnus.acs.ohio-state.edu!math.ohio-state.edu!howland. reston.ans.net!usc!yeshua.marcam.com!siemens!masticol@ucbvax.Berkeley.EDU (Ste ve Masticola)]

mfeldman@seas.gwu.edu (Michael Feldman) writes:

>>Since quicksort was made famous by Hoare (or vice versa), I wonder why
>>it is so universally used (especially in the C community) when Donald
>>Knuth's big 0 statistics clearly show distribution counting is faster.
>>
>Hey Ted, what's big O?

>Mike Feldman

Asymptotic upper bound for growth in complexity, sometimes read as
"order". E.g.: "Heapsort requires O(n log n) comparisons worst case,
where n is the number of items to be sorted." I'm sure you've seen it
before.

Little o, on the other hand, is an asymptotic lower bound, as in,
"Sorting has been proven to require at least o(n log n) comparisons in
the worst case." (BTW, this holds for hashing sorts, too, if you look
at it closely.)

And, to tell you the truth, I don't know what the heck distribution
counting is... :-) Anyone care to enlighten me?

Pedantically yours,
- Steve (masticol@scr.siemens.com).