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: miker3@ix.netcom.com (Mike Rubenstein) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/22 Message-ID: <321baff0.4200479@nntp.ix.netcom.com>#1/1 X-Deja-AN: 175700046 references: <01bb8f1b$ce59c820$32ee6fce@timhome2> <4vfk6b$i6h@krusty.irvine.com> organization: Netcom x-netcom-date: Wed Aug 21 8:01:29 PM CDT 1996 newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-21T20:01:29-05:00 List-Id: tanmoy@qcd.lanl.gov (Tanmoy Bhattacharya) wrote: > In article <4vfk6b$i6h@krusty.irvine.com> > adam@irvine.com (Adam Beneschan) writes: > > AB: >No, but a complex Big-Oh function has *exactly* the same meaning as a > AB: >simpler one in most cases. Calling something a O(f(n)) function means > AB: >saying that (This may not be the technical definition: but this > AB: >expresses the meaning commonly used): > AB: > > AB: > 1) there exists k and N depending on k such that for all n > N, the > AB: > function in question is bounded in absolute value by by k |f(n)|. > AB: > 2) The minimum such k is non-zero. (This is to prevent a O(n) > AB: > function also being classified as a a O(nlogn) for example). > AB: > AB: I've never seen a definition of O(f(n)) that includes anything like > AB: (2). In the mathematical definitions I've seen, O(f(n)) provides only > AB: an upper bound on the value expressed by O-notation, not a lower > AB: bound. Under these definitions, it is perfectly correct (although not > AB: too useful) to say that a linear algorithm is O(n**2) or O(n**3). > > Correct. Number (2) actually exists only to get it closer to common > usage without giving up the asymptotic nature of the definition. FYI, some authors (e.g., Hardy and Wright in "An Introduction to the Theory of Numbers") use a special notation that, unfortunately, does not render well in ASCII to say that two functions have the same order of magnitude (an equal sign with the bars curved and the convex sides facing each other). f and g have the same order of magnitude if there are positive constants A and B such that Af < g < Bf for all arguments in question. Michael M Rubenstein