Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!usc!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: Date: 27 Nov 90 19:53:32 GMT References: <1990Nov20.202143.10746@craycos.com> <6327:Nov2022:30:2490@kramden.acf.nyu.edu> <37256@nigel.ee.udel.edu> <20414:Nov2623:37:2390@kramden.acf.nyu.edu> Reply-To: peter@ficc.ferranti.com (Peter da Silva) Organization: Xenix Support, FICC Lines: 14 In article <20414:Nov2623:37:2390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > Consider, for instance, N strings of total length L. I can sort them in > time O(L). L can be smaller than cN log N---the average length of the > strings might be constant, or asymptotically log log N, or whatever. ^^^^^^^^ In that case you have a maximum upper bound on the number of unique strings you can handle. If you nave N distinct values, the shortest string that can be used to uniquely identify them is log2(n) bits. All you're doing is deciding to use a constant string length and accepting either rather small limits on your data set size or a rather high constant. How did this thread get started anyway? -- Peter da Silva. `-_-' +1 713 274 5180. 'U` peter@ferranti.com