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: 103376,97188312486d4578
X-Google-Attributes: gid103376,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
From: Matt Austern <austern@isolde.mti.sgi.com>
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/21
Message-ID: <fxtu3tw1pi0.fsf@isolde.mti.sgi.com>#1/1
X-Deja-AN: 175517231
references: <DwGoHq.6n7@cwi.nl> <01bb8f1b$ce59c820$32ee6fce@timhome2>
organization: SGI
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-21T00:00:00+00:00
List-Id: <comp.lang.ada>


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