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,WEIRD_PORT autolearn=ham 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: 103376,97188312486d4578 X-Google-Attributes: gid103376,public X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public From: tanmoy@qcd.lanl.gov (Tanmoy Bhattacharya) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/21 Message-ID: X-Deja-AN: 175590164 references: <01bb8f1b$ce59c820$32ee6fce@timhome2> content-type: text/plain organization: Los Alamos National Laboratory 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: 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. AB: AB: Perhaps someone else can provide a different definition? Tanmoy's AB: statement as expressed above isn't precise enough to be a mathematical AB: definition. Perhaps it means that there are two constants, kl and ku, The (1) above is obviously rigorous. The (2) above is completely rigorous statement expressing common usage. The `minimum such k' refers to the minima of the set of allowed k's (i.e. values of k for which an N exists): the minima may not actually belong to the set. AB: such that the value represented by O(f(n)) is between kl |f(n)| and ku AB: |f(n)| for all n > N. This still may not be enough for people who No. That does not capture the common meaning: if an algorithm is trivial for odd N, but goes as N^2 for even N, it is still called O(N^2). But, naturally, you can't find kl in this case. AB: want O(f(n)) to give an approximation of proportional running time, so AB: those people may want to add the restriction that kl/ku >= 0.95 or AB: something to keep the running time from varying too much. And Tim AB: wants a notation that puts bounds on the running time for *all* n, not AB: just "large enough" n. Yes if you want O() to be an approximation, you may want to use your kl/ku solution. AB: AB: The more I follow this thread, the more I'm convinced that our use of AB: O-notation is an abuse; we've twisted the original mathematical AB: purpose of the notation beyond recognition. The first place I saw AB: this notation used was in Knuth's _Art of Computer Programming_, and AB: he only used it to express part of a formula that approaches zero as n AB: gets large. For example: AB: AB: P(n) = sqrt(pi*n/2) - 2/3 + (11/24)*sqrt(pi/(2*n)) + 4/(135*n) AB: - (71/1152)*sqrt(pi/(2*n**3)) + O(n**-2) AB: AB: Here, O(n**-2) refers to terms in the sum that eventually go to zero AB: as n gets large. From what I could find, Knuth *never* uses it to AB: describe the running time of an algorithm. AB: AB: Following this viewpoint, when we computer scientists speak of an AB: algorithm's running time as O(n**2), mathematicians might say AB: AB: Running time = K * n**2 * (1 + O(1/n)) AB: AB: for some constant K. The point here is that the proportional AB: difference between the running time and (K * n**2) tends to disappear AB: as n gets large (hence the O(1/n) term). AB: And as you can trivially show, the K in the above formula is the minima of the set of k's that I was talking about. The two points of view are identical. Except, when I (or almost anyone) calls something O(N^2), the correction term need not be O(N): it may as well be O(NlogN). AB: In contrast to what I believe was the original purpose of O-notation, AB: computer scientists are using the notation as a shorthand for AB: "approximately proportional to." The original mathematical No. It is used mainly in the theory of algorithmic complexity. Its use as an approximation is only a loose usage: which is often, but not always, correct. AB: definition, which suited the purpose of expressing a quantity that AB: tended toward zero, doesn't suit our purposes of classifying The O notation is used for both small and large quantities. Its original definition was that f(x) and g(x) were the same `order' if lim f(x)/g(x) was neither 0 nor infinite as x went to something. This definition can be easily modified if the limit does not exist, and I think my definition is identical to that variation as long as we talk about O(f) only for functions f that are monotonic for sufficiently large N. AB: P.S. My theories about how mathematicians view and use O-notation may AB: be incorrect. I might ask sci.math to enlighten me here. --ajb Yes, the topic has gone far beyond the purview of most of the groups: let us take this discussion elsewhere. Cheers Tanmoy -- tanmoy@qcd.lanl.gov(128.165.23.46) DECNET: BETA::"tanmoy@lanl.gov"(1.218=1242) Tanmoy Bhattacharya O:T-8(MS B285)LANL,NM87545 H:#9,3000,Trinity Drive,NM87544 Others see , or. -- fax: 1 (505) 665 3003 voice: 1 (505) 665 4733 [ Home: 1 (505) 662 5596 ]