Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: 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

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