Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!cbatt!gatech!lll-lcc!seismo!rochester!ken
From: ken@rochester.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc
Subject: Re: Information on order(N) sort
Message-ID: <25438@rochester.ARPA>
Date: Sun, 1-Mar-87 16:09:07 EST
Article-I.D.: rocheste.25438
Posted: Sun Mar  1 16:09:07 1987
Date-Received: Mon, 2-Mar-87 22:58:23 EST
References: <814@fmsrl7.UUCP> <175@ucdavis.UUCP> <9638@topaz.RUTGERS.EDU> <2013@mmintl.UUCP>
Reply-To: ken@rochester.UUCP (SKY)
Organization: U of Rochester, CS Dept, Rochester, NY
Lines: 13
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:130 comp.lang.misc:310 comp.os.misc:45

The Design and Analysis of Computer Algorithms (Aho, Hopcroft and
Ullman?) makes it clear that when making a time analysis you must state
the cost of a basic operation and what n measures. Normally one of two
possible assumptions is used: constant cost and log cost. If all the
data points fit within a machine word or constant multiple thereof, the
constant cost criterion is the one to use. If you expect to deal with
data of unbounded size, say arbitary precision arithmetic, log cost is
the appropriate choice.

Comparison sorting is O(n log n) under the constant cost assumption,
where n is the number of items.

	Ken