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: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,public
X-Google-Thread: fc89c,97188312486d4578
X-Google-Attributes: gidfc89c,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
X-Google-Thread: 103376,97188312486d4578
X-Google-Attributes: gid103376,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/23
Message-ID: <4vj114$bch@goanna.cs.rmit.edu.au>#1/1
X-Deja-AN: 175920215
distribution: inet
references: <01bb8f6f$46bc2da0$87ee6fce@timpent.airshields.com>
 <4vg7m8$7u5@goanna.cs.rmit.edu.au> <4vhmmv$hdg@news1.mnsinc.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-23T00:00:00+00:00
List-Id: <comp.lang.ada>


huang@mnsinc.com (Szu-Wen Huang) writes:

>O() has nothing to do with the cases.

You have one end of the stick.
  The end you have is "you can correctly and idiomatically use big-Oh
  when discussing the asymptotic cost of any case."

But it was the OTHER end we were talking about.
  The end you have missed is "when you say that an algorithm is big-Oh of
  something WITHOUT SAYING WHICH CASE YOU ARE TALKING about the normal
  implicature is that you are talking about the WORST case."

>You can express either best, average, or worst case scenarios
>using the notation.

Nobody has disputed this.  You _can_.  The question was which case is
normally *implied* by a mention of big-Oh without explicit mention of
the case.  For example, "chairman" *CAN* be used to refer to a man
(Mr Chairman) or a woman (Madam Chairman) but it is today argued that
since it is normally taken to imply a man *if you don't specify which*
it is therefore rude to use it.

It's just like the fact that you *can* say
	f(x) = O(g(x)) as x -> infinity
or	f(x) = O(g(x)) as x -> 0
but if you don't *say explicitly* where x is headed, the conventional
implication is that x is headed for +infinity.

>I believe Tim arguing that f(n) in O(f(n)) is assumed to be continuous
>unless specified.

Eh?  Big-Oh notation comes from the calculus, so when one talks about
O(f(x)) continuity might (or might not, the definition of big-Oh doesn't
care in the least) be relevant.  But when you are talking about O(f(n)),
the conventional implication is that n is an integer, and I'm not quite
sure what you mean by a continuous function from the (discrete!) natural
numbers.  Trivial topology?  Scott topology?  What?

-- 
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.