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: ark@research.att.com (Andrew Koenig)
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/22
Message-ID: <DwJHv8.IH5@research.att.com>#1/1
X-Deja-AN: 175825283
references: <01bb8f1b$ce59c820$32ee6fce@timhome2>
 <TANMOY.96Aug21083507@qcd.lanl.gov> <4vfk6b$i6h@krusty.irvine.com>
organization: AT&T Research, Murray Hill NJ
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>


In article <4vfk6b$i6h@krusty.irvine.com> adam@irvine.com (Adam Beneschan) writes:

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

`The Art of Computer Programming,' Vol. 3, page 90:

	Thus we can make a substantial improvement over straight
	insertion, from O(N^2) to O(N^1.667), just by using Shell's
	method with two increments.

Page 142:

	This idea is called quadratic selection; its total
	execution time is O(N*sqrt(N)), which is substantially
	better than order N^2.

And so on.
-- 
				--Andrew Koenig
				  ark@research.att.com