🚀 go-pugleaf

In article <4343:Nov2720:36:5790@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
> In article <1B779_7@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes:
> > 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?

> Yes. In constant time. Why anyone would want to use eight passes with
> lots of bit manipulation where one much simpler pass would suffice, I
> don't know.

OK, you then need to use 8 passes. With a larger sample size you need
to use more passes. The number of passes increase as the log of the
sample size.

So, you need log(n) passes, and each pass takes O(n) time. QED.

All you're doing is changing the constant in O(n log n) (or the base of
the logarithm, which comes to the same thing).
-- 
Peter da Silva.   `-_-'
+1 713 274 5180.   'U`
peter@ferranti.com