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: "Dann Corbit" <a-cnadc@microsoft.com>
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/20
Message-ID: <01bb8eeb$11e06d00$2bac399d@v-cnadc1>#1/1
X-Deja-AN: 175406998
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>
organization: Microsoft Corporation
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-20T00:00:00+00:00
List-Id: <comp.lang.ada>




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.

Definitions:
n = number of elements
m = slope in units/second
t = time in seconds
b = some constant number of seconds

What is really demanded for an algorithm O(n) is that

	t <= m*n + b

for some constants m and b.