Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!caip!lll-crg!lll-lcc!qantel!hplabs!tektronix!uw-beaver!ubc-vision!alberta!calgary!radford
From: radford@calgary.UUCP (Radford Neal)
Newsgroups: net.arch
Subject: Re: One really good use for BIG core memory (address sort)
Message-ID: <403@vaxb.calgary.UUCP>
Date: Sun, 28-Sep-86 21:04:59 EDT
Article-I.D.: vaxb.403
Posted: Sun Sep 28 21:04:59 1986
Date-Received: Thu, 2-Oct-86 19:34:47 EDT
References: <600@sdcc12.UUCP> <7960@lanl.ARPA> <5559@decwrl.DEC.COM>
Organization: U. of Calgary, Calgary, Ab.
Lines: 8
Summary: Bucket sort is really O(nlogn)

RE: Discussion of bucket sorting at a use for huge memories.

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.

    Radford Neal
    The University of Calgary