Article View: comp.lang.misc
Article #2224Re: Lying
From: Richard A. O'Keefe
Date: Mon, 26 Nov 1990 09:24
Date: Mon, 26 Nov 1990 09:24
13 lines
1126 bytes
1126 bytes
In article <246@smds.UUCP>, rh@smds.UUCP (Richard Harter) writes: > 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.] This applies to *all* "in-core" sorting methods. It's not that the sorting method breaks down, but that the "array access is constant time" assumption breaks down. That also applies to things like matrix multiplication! One can use samples (as one does in linear-time selection algorithms) to partition the collection into manageable pieces. -- I am not now and never have been a member of Mensa. -- Ariadne.
Technical Details
Message-ID:
<4372@goanna.cs.rmit.oz.au>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!samsung!munnari.oz.au!goanna!okReferences:
<6097@lanl.gov> <4298@goanna.cs.rmit.oz.au> <246@smds.UUCP>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!samsung!munnari.oz.au!goanna!ok From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) Newsgroups: comp.lang.misc Subject: Re: Lying Message-ID: <4372@goanna.cs.rmit.oz.au> Date: 26 Nov 90 09:24:51 GMT References: <6097@lanl.gov> <4298@goanna.cs.rmit.oz.au> <246@smds.UUCP> Organization: Comp Sci, RMIT, Melbourne, Australia Lines: 13