From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.5-pre1 (2020-06-20) on
	ip-172-31-74-118.ec2.internal
X-Spam-Level: 
X-Spam-Status: No, score=-0.5 required=3.0 tests=BAYES_05 autolearn=ham
	autolearn_force=no version=3.4.5-pre1
Date: 9 Sep 93 21:33:25 GMT
From: utcsri!relay.cs.toronto.edu!neat.cs.toronto.edu!cs.toronto.edu!tlai@uunet
.uu.net  (Tony W H Lai)
Subject: sorting bounds (was: Re: Hoare's gripes about Ada)
Message-ID: <93Sep9.173300edt.48148@neat.cs.toronto.edu>
List-Id: <comp.lang.ada>

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.