Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!lavaca.uh.edu!menudo.uh.edu!sugar!ficc!peter
From: peter@ficc.ferranti.com (Peter da Silva)
Newsgroups: comp.lang.misc
Subject: Re: Sorting bounds
Message-ID: <1B779_7@xds13.ferranti.com>
Date: 25 Nov 90 18:40:20 GMT
References: <1990Nov20.202143.10746@craycos.com> <6327:Nov2022:30:2490@kramden.acf.nyu.edu> <1990Nov21.211000.11359@craycos.com> <29686:Nov2505:33:4290@kramden.acf.nyu.edu>
Reply-To: peter@ficc.ferranti.com (Peter da Silva)
Organization: Xenix Support, FICC
Lines: 13

In article <29686:Nov2505:33:4290@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
> I'm sorry I didn't dismiss this strongly enough in my first response. It
> is absolutely irrelevant how long it takes to pick one of N buckets. All
> radix sort uses is picking one of a constant number (you said K at
> first) of buckets. For definiteness, let's settle upon K as being 256
> for all time. It takes constant time, in theory and in practice, to
> select one of 256 buckets.

How about picking 2 buckets? Does it still work? In constant time?

Would it not be safe to assume that it takes O(log(key length)) time to do
something with the bucket once you've found it, assuming that the key length
is greater than log2(buckets)?
-- 
Peter da Silva.   `-_-'
+1 713 274 5180.   'U`
peter@ferranti.com