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: dewar@cs.nyu.edu (Robert Dewar)
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/25
Message-ID: <dewar.840990731@schonberg>#1/1
X-Deja-AN: 176397622
references: <4umeot$re2@hil-news-svc-2.compuserve.com>
 <dewar.839831192@schonberg> <4v2fb9$lpj@news.utdallas.edu>
 <4v2qkd$40f@news1.mnsinc.com> <dewar.840305735@schonberg>
 <4vd05f$rt5@news1.mnsinc.com> <01bb8eeb$11e06d00$2bac399d@v-cnadc1>
 <01bb8f6f$46bc2da0$87ee6fce@timpent.airshields.com>
 <4vg7m8$7u5@goanna.cs.rmit.edu.au>
organization: Courant Institute of Mathematical Sciences
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-25T00:00:00+00:00
List-Id: <comp.lang.ada>


Richard says

"The normal use of big-Oh when discussing running time is to give
 - an asymptotic
 - upper bound
 - for the worst case."

In practice, this is not at all always true, for isntance you will often
see people refer to quicksort as O(N.logN) without qualifying it with
average case, so I think the best thing is (a) when using big-O notatoin,
always qualify it with worst or average case and (b) when reading big-O
notation without such a qualification, do not assume that it is necessarily
worst or average case, but reserve judgmnent!