From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: ***
X-Spam-Status: No, score=3.8 required=5.0 tests=BAYES_00,INVALID_MSGID,
	RATWARE_MS_HASH,RATWARE_OUTLOOK_NONAME autolearn=no autolearn_force=no
	version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,public
X-Google-Thread: fc89c,97188312486d4578
X-Google-Attributes: gidfc89c,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
X-Google-Thread: 103376,97188312486d4578
X-Google-Attributes: gid103376,public
From: "Tim Behrendsen" <tim@airshields.com>
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/21
Message-ID: <01bb8f6f$46bc2da0$87ee6fce@timpent.airshields.com>#1/1
X-Deja-AN: 175613867
references: <4umeot$re2@hil-news-svc-2.compuserve.com>
 <dewar.839831192@schonberg> <4v2fb9$lpj@news.utdallas.edu>
 <4v2qkd$40f@news1.mnsinc.com> <dewar.840305735@schonberg>
 <4vd05f$rt5@news1.mnsinc.com> <01bb8eeb$11e06d00$2bac399d@v-cnadc1>
content-type: text/plain; charset=ISO-8859-1
organization: A-SIS
mime-version: 1.0
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-21T00:00:00+00:00
List-Id: <comp.lang.ada>


Dann Corbit <a-cnadc@microsoft.com> wrote in article
<01bb8eeb$11e06d00$2bac399d@v-cnadc1>...
> 
> Szu-Wen Huang <huang@mnsinc.com> wrote in article
> <4vd05f$rt5@news1.mnsinc.com>...
> {snip}
> > I disagree.  I expect a linear algorithm to display linear behavior
> > unless otherwise stated.  What you cite is a case where it needs to
> > be explicitly stated, because calling that algorithm "O(n)" is next
> > to useless in predicting its behavior without knowing this peculiar
> > behavior at n=1,000.  IOW, this prediction holds if I'm predicting
> > for n in (0, 1,000] and (1,000, infinity), and will hold for other
> > algorithms that do not have this peculiarity.
> 
> Nonetheless, it only has to be true in the limiting case.
> Try, for instance, some O(n*log(n) ) algorithm like heapsort
> on data that is random, ordered, reverse ordered, sawtooth, etc,
> and you will find that it takes different amounts of time even for
> the same number of input values.
> 
> Or take quicksort, which is worst case O(n*n) and you will
> see that it usually plots as approximately O(n*log(n)), but
> can even appear to be linear for some special data sets and 
> algorithm implementations.

Well, but look at your own terminology.  You describe quicksort
as "worst case O(n*n)" and (paraphrase) "average case O(n*log(n))".
When the Big-Oh is given for a particular algorithm without
any qualification, it is usually assumed to be the average
behavior over the data set.  The point is not that O() makes
absolute time predictions, but that it gives *behavior*
predictions.