Article View: comp.lang.misc
Article #2238Re: Sorting bounds
From: Peter da Silva
Date: Sun, 25 Nov 1990 18:40
Date: Sun, 25 Nov 1990 18:40
17 lines
1432 bytes
1432 bytes
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
Technical Details
Message-ID:
<1B779_7@xds13.ferranti.com>Path:
arc1-ca.pugleaf.net!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!peterReferences:
<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>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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