* sorting bounds (was: Re: Hoare's gripes about Ada)
@ 1993-09-09 21:33 Tony W H Lai
0 siblings, 0 replies; only message in thread
From: Tony W H Lai @ 1993-09-09 21:33 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~1993-09-09 21:33 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
1993-09-09 21:33 sorting bounds (was: Re: Hoare's gripes about Ada) Tony W H Lai
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox