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: huang@mnsinc.com (Szu-Wen Huang)
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/22
Message-ID: <4vhmmv$hdg@news1.mnsinc.com>#1/1
X-Deja-AN: 175824784
distribution: inet
references: <01bb8f6f$46bc2da0$87ee6fce@timpent.airshields.com>
 <4vg7m8$7u5@goanna.cs.rmit.edu.au>
followup-to: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
organization: Monumental Network Systems
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-22T00:00:00+00:00
List-Id: <comp.lang.ada>


Richard A. O'Keefe (ok@goanna.cs.rmit.edu.au) wrote:
: "Tim Behrendsen" <tim@airshields.com> 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).

O() has nothing to do with the cases.  You can express either best,
average, or worst case scenarios using the notation.  I believe Tim
arguing that f(n) in O(f(n)) is assumed to be continuous unless
specified.

[snip]