Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!columbia!rutgers!caip!clyde!ima!johnl
From: johnl@ima.UUCP (John R. Levine)
Newsgroups: net.arch
Subject: Re: One really good use for BIG core memory (address sort)
Message-ID: <236@ima.UUCP>
Date: Fri, 3-Oct-86 19:06:23 EDT
Article-I.D.: ima.236
Posted: Fri Oct  3 19:06:23 1986
Date-Received: Mon, 6-Oct-86 18:42:17 EDT
References: <600@sdcc12.UUCP> <7960@lanl.ARPA> <5559@decwrl.DEC.COM> <403@vaxb.calgary.UUCP> <15878@ucbvax.BERKELEY.EDU>
Reply-To: johnl@ima.UUCP (John R. Levine)
Organization: Javelin Software Corporation
Lines: 17
Summary: it is not O(n log n)

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.

Not really true -- memory addresses are not decoded by a tree but more
typically by broadcasting the address and having all of the memory units
look for their own addresses in parallel.  More realistically, by the time
you take into account caches, pipelined buses, interleaved memory and all
the other speed up tricks commonly done in hardware, the address decode time
is the least of your problems.
-- 
John R. Levine, Javelin Software Corp., Cambridge MA +1 617 494 1400
{ ihnp4 | decvax | cbosgd | harvard | yale }!ima!johnl, Levine@YALE.EDU
The opinions expressed herein are solely those of a 12-year-old hacker
who has broken into my account and not those of any person or organization.