Article View: comp.lang.misc
Article #2150Re: Lying
From: Richard Harter
Date: Sat, 17 Nov 1990 08:36
Date: Sat, 17 Nov 1990 08:36
21 lines
1471 bytes
1471 bytes
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.
Technical Details
Message-ID:
<246@smds.UUCP>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!know!sdd.hp.com!wuarchive!husc6!m2c!jjmhome!smds!rhReferences:
<6097@lanl.gov> <4298@goanna.cs.rmit.oz.au>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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