Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!know!sdd.hp.com!wuarchive!husc6!m2c!jjmhome!smds!rh
From: rh@smds.UUCP (Richard Harter)
Newsgroups: comp.lang.misc
Subject: Re: Lying
Summary: Linear time with qualifications
Message-ID: <246@smds.UUCP>
Date: 17 Nov 90 08:36:31 GMT
References: <6097@lanl.gov> <4298@goanna.cs.rmit.oz.au>
Organization: SMDS Inc., Concord, MA
Lines: 21

In article <4298@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:

> I like it a lot.  Section 9.4 says on p180
> 	Bucket sort runs in linear time on the average.  ...
> 	bucket sort assumes that that the input is generated by
> 	a random process that distributes elements uniformly
> 	over the interval [0,1).
> They explicitly use the formula O(n), where n is the number of keys.

The good news is that you don't need uniformity - almost any relatively
smooth distribution will do.  The bad news is that many real life
sorting problems are distinctly not smooth.

It should also be noted that bucket sorts, distribution sorts, math sorts,
et. al. are linear only within a range.  [If the file size is large enough
the implicit assumptions about short data access times fail.]
-- 
Richard Harter, Software Maintenance and Development Systems, Inc.
Net address: jjmhome!smds!rh Phone: 508-369-7398 
US Mail: SMDS Inc., PO Box 555, Concord MA 01742
This sentence no verb.  This sentence short.  This signature done.