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: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public 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 From: "Tim Behrendsen" Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/21 Message-ID: <01bb8faa$138adae0$87ee6fce@timpent.airshields.com>#1/1 X-Deja-AN: 175547431 references: <01bb8f1b$ce59c820$32ee6fce@timhome2> <4vfk6b$i6h@krusty.irvine.com> content-type: text/plain; charset=ISO-8859-1 organization: A-SIS 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: Matt Austern wrote in article ... > adam@irvine.com (Adam Beneschan) writes: > > > 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. > > Yes he does. Theorem P, for example, in section 5.2.1, says that the > running time of shell sort (using a specific increment sequence) is > O(N^(3/2)). This statement is correct and precise: it means that > there exists some positive constant C such that, for sufficiently > large N, the running time of shell sort is less than C N^(3/2). > > Part of this confusion might be that some people say O(N) when they > really mean Theta(N). See section 2.1 of Cormen, Leiserson, and > Rivest for the distinction between O(N), Theta(N), and Omega(N). Interestingly, in section 5.2.2, he uses O() notation in the actual running time computation for bubble sort: "... so the MIX running time is 8A + 7B + 8C + 1 = (min 8N + 1, ave 5.75N^2 + O(N ln N), max 7.5N^2 + 0.5N + 1)." Reading on to the section on Asymptotic Methods, he goes into some very heavy duty math involving the asymptotic behavior of bubble sort. Egad! I never thought you could generate so much calculus from lowly bubble sort. I think you're right, however. The O() notation is all over his analysis in non-trivial ways, such as my favorite: O( N^(1/2) * e^(-pi*N/2) * integral(-1.5 -> M, N^t dt) ), if 2^iN != 1. Obviously, O() is being used in a precise mathematical way, rather than the informal use that it's normally put to. -- Tim Behrendsen (tim@airshields.com)