Article View: net.arch
Article #2954Re: One really good use for BIG core memory (address sort)
From: David desJardins
Date: Wed, 01 Oct 1986 09:41
Date: Wed, 01 Oct 1986 09:41
14 lines
1402 bytes
1402 bytes
In article <403@vaxb.calgary.UUCP> radford@calgary.UUCP (Radford Neal) writes: > >Bucket sort is not O(n) in time, nor O(k), but O(nlogn). This is >because the time required to decode the addresses for your huge >memories is logarithmic in the size of the memory. This doesn't really seem like a fair characterization, because the logarithmic penalty for the actual comparisons/moves/calculations are built into all sorting algorithms. It is just as true that it takes time O(log n) for a quicksort to exchange two entries. You have to specify the units to be used, and the usual choice is single machine operations such as comparison or exchange, which take logarithmic time. -- David desJardins
Technical Details
Message-ID:
<15878@ucbvax.BERKELEY.EDU>Path:
arc1-ca.pugleaf.net!utzoo!mnetor!seismo!ll-xn!nike!ucbcad!ucbvax!brahms!desjReferences:
<600@sdcc12.UUCP> <7960@lanl.ARPA> <5559@decwrl.DEC.COM> <403@vaxb.calgary.UUCP>Show Full Headers
Complete Article Headers
Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: arc1-ca.pugleaf.net!utzoo!mnetor!seismo!ll-xn!nike!ucbcad!ucbvax!brahms!desj From: desj@brahms.BERKELEY.EDU (David desJardins) Newsgroups: net.arch Subject: Re: One really good use for BIG core memory (address sort) Message-ID: <15878@ucbvax.BERKELEY.EDU> Date: Wed, 1-Oct-86 05:41:51 EDT Article-I.D.: ucbvax.15878 Posted: Wed Oct 1 05:41:51 1986 Date-Received: Fri, 3-Oct-86 00:38:32 EDT References: <600@sdcc12.UUCP> <7960@lanl.ARPA> <5559@decwrl.DEC.COM> <403@vaxb.calgary.UUCP> Sender: usenet@ucbvax.BERKELEY.EDU Reply-To: desj@brahms.UUCP (David desJardins) Organization: University of California, Berkeley Lines: 14