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: fc89c,97188312486d4578
X-Google-Attributes: gidfc89c,public
X-Google-Thread: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,public
X-Google-Thread: 103376,97188312486d4578
X-Google-Attributes: gid103376,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,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/21
Message-ID: <01bb8f81$ecbec8e0$2bac399d@v-cnadc1>#1/1
X-Deja-AN: 175657314
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>
 <01bb8f6f$46bc2da0$87ee6fce@timpent.airshields.com>
organization: Microsoft Corporation
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>




Tim Behrendsen <tim@airshields.com> wrote in article
<01bb8f6f$46bc2da0$87ee6fce@timpent.airshields.com>...
{snip}
> 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.
> 
True, but only in the limiting case.  An algorithm
that is O(n) has **some** line that lies above all
time values for the function with finite slope and
intercept.  And an O(n*n) algorithm has **some **
parabola that lies above the function for all values
of n.   It is, of course, possible for linear algorithms
to be unusable if the slope is nearly infinite, or
the intercept is nearly infinite, or for exponential
algorithms or even factorial algorithms to be
usable if there is a constant multiplier small enough
to pull the curve down into the usable range for
a useful domain.

In short, O(f(n)) does not tell the whole story, even
when we know what f(n) is.  It's still a good idea to
benchmark the algorithm for your domain values
against competing algorithms, unless someone
has already done it for you.