Article View: comp.lang.misc
Article #4686Information on order(N) sort
From: drw
Date: Sat, 28 Feb 1987 19:22
Date: Sat, 28 Feb 1987 19:22
17 lines
1268 bytes
1268 bytes
stephen@datacube.UUCP writes: > This is absolutely wrong. The size of the key associated with an item > is entirely independent of the number of bits required to address that > item. The radix sort is O( n log M ) in time, where log M is the size > of the key in bits. It is easy to envision sorting an array of 1 million > 8 bit keys, in which case the algorithm would be O( 8*n ), not O(20*n). Yeah, but you have to be able to *address* all 1 million records in some way or another (unless you are storing them on tape!). That requires 20 bit addresses, minimum. Even if your keys are small, the addresses of the records will eventually bring in the log N factor. Dale -- Dale Worley Cullinet Software UUCP: ...!seismo!harvard!mit-eddie!cullvax!drw ARPA: cullvax!drw@eddie.mit.edu
Technical Details
Message-ID:
<860@cullvax.UUCP>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!water!watnot!watmath!clyde!rutgers!husc6!necntc!cullvax!drwShow Full Headers
Complete Article Headers
Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: arc1-ca.pugleaf.net!utzoo!utgpu!water!watnot!watmath!clyde!rutgers!husc6!necntc!cullvax!drw From: drw@cullvax.UUCP Newsgroups: comp.lang.misc Subject: Information on order(N) sort Message-ID: <860@cullvax.UUCP> Date: Sat, 28-Feb-87 14:22:59 EST Article-I.D.: cullvax.860 Posted: Sat Feb 28 14:22:59 1987 Date-Received: Sun, 1-Mar-87 17:05:34 EST Organization: Cullinet Software, Inc., Westwood, MA Lines: 17