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: 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 X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public From: ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/22 Message-ID: <4vg7m8$7u5@goanna.cs.rmit.edu.au>#1/1 X-Deja-AN: 175569305 references: <4umeot$re2@hil-news-svc-2.compuserve.com> <4v2fb9$lpj@news.utdallas.edu> <4v2qkd$40f@news1.mnsinc.com> <4vd05f$rt5@news1.mnsinc.com> <01bb8eeb$11e06d00$2bac399d@v-cnadc1> <01bb8f6f$46bc2da0$87ee6fce@timpent.airshields.com> organization: Comp Sci, RMIT, Melbourne, Australia newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada nntp-posting-user: ok Date: 1996-08-22T00:00:00+00:00 List-Id: "Tim Behrendsen" writes: >Well, but look at your own terminology. You describe quicksort >as "worst case O(n*n)" and (paraphrase) "average case O(n*log(n))". >When the Big-Oh is given for a particular algorithm without >any qualification, it is usually assumed to be the average >behavior over the data set. This is news to me. In fact, it shocked me so much that I went back to a recent textbook (Cormen, Leiserson, and Rivest) to check. They say What me mean when we say "the running time is O(n^2 )" is that the WORST-CASE running time (which is a function of n) is O(n^2), or equivalently, no matter what particular input of size n is chosen for each value of n, the running time on that set of inputs is O(n^2). >The point is not that O() makes absolute time predictions, but that it >gives *behavior* predictions. The normal use of big-Oh when discussing running time is to give - an asymptotic - upper bound - for the worst case. Since "average" running time for any nontrivial algorithm (such as a sort) is totally meaningless unless you specify the distribution of the inputs, "average" times are the linguistically "marked" case and by the usual maxims is the case which gets specially highlighted. That is, if you want to talk about average running times, you have to - SPECIFY A DISTRIBUTION and - *say* AVERAGE run time. -- Australian citizen since 14 August 1996. *Now* I can vote the xxxs out! Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.