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.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	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: pete@borland.com (Pete Becker)
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/21
Message-ID: <4vfe33$dg6@druid.borland.com>#1/1
X-Deja-AN: 175656067
references: <4v2qkd$40f@news1.mnsinc.com> <dewar.840305735@schonberg>
 <4vd05f$rt5@news1.mnsinc.com> <DwGoHq.6n7@cwi.nl>
 <01bb8f1b$ce59c820$32ee6fce@timhome2>
content-type: Text/Plain; charset=ISO-8859-1
organization: Borland International
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>


In article <01bb8f1b$ce59c820$32ee6fce@timhome2>, tim@airshields.com says...
>
>> 
>> But big-oh notation is about prediction for large n.  You can not use
>> the notation to really predict the running time for a particular value,
>> only to estimate it; and your estimation may be way off.  If an
>> algorithm runs in N^2 + 10^100 N seconds, it is still O(N^2), although
>> you never will experience the quadratic behaviour of the algorithm.
>> (Actually, of course, you will never see the algorithm come to
>completion.)
>
>I have to admit, I have to side with Szu-Wen.  I've never really
>thought about this case for the O() notation, but it seems from
>a purely mathematical standpoint that O(f(n)) means that f(n)
>is *the* function.  If f(n) happens to be a non-continuous function,
>then so be it.
>
>If the running time is
>
>    kn for n < 1000
>    k(n^2) for n >= 1000
>
>then f(n) =
>    O(n) for n < 1000
>    O(n^2) for n >= 1000
>
>then the big-Oh function should be (pardon my syntax)
>
>    O( (n < 1000) ? n : n^2 )
>
>The latter is not only more useful, but absolutely accurate.
>AFAIK, there are no limits on the complexity of the Big-Oh
>function, and no requirement that it be a continuous
>function.

No. The point is that this notation talks about asymptotic behavior, not 
behavior for specific cases. If you want to talk about more complex notions, 
feel free, but don't use O() notation to talk about them, because you will 
confuse people when you misuse this notation. In particular, note that

f(x) = 100000*x + x*x

is linear for small values of x, and quadratic for large values. O(f(x)) is 
O(x^2), however, because eventually the x^2 term dominates.