sorting bounds (was: Re: Hoare's gripes about Ada)

[utcsri!relay.cs.toronto.edu!neat.cs.toronto.edu!cs.toronto.edu!tlai@uunet .uu.net (Tony W H Lai)]

In article <263mb7$mpd@schonberg.cs.nyu.edu> dewar@cs.nyu.edu (Robert Dewar) wr
ites:
>Boy this is getting off the topic, but it's hard to stand by quietly and
>see blatantly incorrect technical comments.
>
>"Sorting has been proved to take O(n log n) time"
>
>is plain wrong. This bound applies only if the sorting is restricted to
>comparisons. [stuff deleted]

Technically, the statement is true (for random access machines).  The O
notation is used for upper bounds, while \Omega is used for lower bounds.
This has absolutely nothing to do with Ada, so I've set the followups
appropriately.