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=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	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: 103376,97188312486d4578
X-Google-Attributes: gid103376,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
From: adam@irvine.com (Adam Beneschan)
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/21
Message-ID: <4vfk6b$i6h@krusty.irvine.com>
X-Deja-AN: 175512501
references: <DwGoHq.6n7@cwi.nl> <01bb8f1b$ce59c820$32ee6fce@timhome2>
 <TANMOY.96Aug21083507@qcd.lanl.gov>
organization: /z/news/newsctl/organization
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>


tanmoy@qcd.lanl.gov (Tanmoy Bhattacharya) writes:
 
 >In article <01bb8f1b$ce59c820$32ee6fce@timhome2>
 >"Tim Behrendsen" <tim@airshields.com> writes:
 ><snip>
 >B: I have to admit, I have to side with Szu-Wen.  I've never really
 >B: thought about this case for the O() notation, but it seems from
 >B: a purely mathematical standpoint that O(f(n)) means that f(n)
 >B: is *the* function.  If f(n) happens to be a non-continuous function,
 > 
 >It is not a question of convenience or usefulness: it is a question of
 >definitions. As is almost universally defined defined, O(n^2+n) and
 >O(n^2) mean exactly the same, as does
 >
 ><snip>
 >B: 
 >B:     O( (n < 1000) ? n : n^2 )
 >B: 
 >
 >and hence when you write it instead of the more easily read O(n^2), it
 >tells people that you do not know the meaning of O().
 >
 >B: The latter is not only more useful, but absolutely accurate.
 >
 >Which is irrelevant. Use, a different notation if you want to invent a
 >new concept: a concept that is more useful in what you want to do. 
 >
 >B: AFAIK, there are no limits on the complexity of the Big-Oh
 >B: function, and no requirement that it be a continuous
 >B: function.
 >
 >No, but a complex Big-Oh function has *exactly* the same meaning as a
 >simpler one in most cases. Calling something a O(f(n)) function means
 >saying that (This may not be the technical definition: but this
 >expresses the meaning commonly used):
 >
 >  1) there exists k and N depending on k such that for all n > N, the
 >     function in question is bounded in absolute value by by k |f(n)|. 
 >  2) The minimum such k is non-zero. (This is to prevent a O(n)
 >     function also being classified as a a O(nlogn) for example).

I've never seen a definition of O(f(n)) that includes anything like
(2).  In the mathematical definitions I've seen, O(f(n)) provides only
an upper bound on the value expressed by O-notation, not a lower
bound.  Under these definitions, it is perfectly correct (although not
too useful) to say that a linear algorithm is O(n**2) or O(n**3).

Perhaps someone else can provide a different definition?  Tanmoy's
statement as expressed above isn't precise enough to be a mathematical
definition.  Perhaps it means that there are two constants, kl and ku,
such that the value represented by O(f(n)) is between kl |f(n)| and ku
|f(n)| for all n > N.  This still may not be enough for people who
want O(f(n)) to give an approximation of proportional running time, so
those people may want to add the restriction that kl/ku >= 0.95 or
something to keep the running time from varying too much.  And Tim
wants a notation that puts bounds on the running time for *all* n, not
just "large enough" n.

The more I follow this thread, the more I'm convinced that our use of
O-notation is an abuse; we've twisted the original mathematical
purpose of the notation beyond recognition.  The first place I saw
this notation used was in Knuth's _Art of Computer Programming_, and
he only used it to express part of a formula that approaches zero as n
gets large.  For example:

P(n) = sqrt(pi*n/2) - 2/3 + (11/24)*sqrt(pi/(2*n)) + 4/(135*n)
         - (71/1152)*sqrt(pi/(2*n**3)) + O(n**-2)

Here, O(n**-2) refers to terms in the sum that eventually go to zero
as n gets large.  From what I could find, Knuth *never* uses it to
describe the running time of an algorithm. 

Following this viewpoint, when we computer scientists speak of an
algorithm's running time as O(n**2), mathematicians might say

    Running time = K * n**2 * (1 + O(1/n))

for some constant K.  The point here is that the proportional
difference between the running time and (K * n**2) tends to disappear
as n gets large (hence the O(1/n) term).  

In contrast to what I believe was the original purpose of O-notation,
computer scientists are using the notation as a shorthand for
"approximately proportional to."  The original mathematical
definition, which suited the purpose of expressing a quantity that
tended toward zero, doesn't suit our purposes of classifying
algorithms by approximate running time, and for predicting how long
our programs will run for.  Sure, we can augment the definition to
meet our needs, but then we all have arguments about what O-notation
really means, since there's no standard any more.  (Furthermore, the
changed definitions may mean that O-notation no longer has some of the
mathematical properties that mathematicians make use of when working
with O-notation.)

So maybe it's time we all admit that our use of O-notation conforms to
neither the original purpose nor the original definition of the
notation.  With that in mind, perhaps we should invent our own
notation or notations, with definitions we can all standardize on.

\end{overly-academic-nitpicking}

                                -- Adam

P.S. My theories about how mathematicians view and use O-notation may
be incorrect.  I might ask sci.math to enlighten me here.   --ajb