Article View: comp.lang.misc
Article #2247Re: Sorting bounds
From: Peter da Silva
Date: Tue, 27 Nov 1990 19:53
Date: Tue, 27 Nov 1990 19:53
18 lines
1409 bytes
1409 bytes
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
Technical Details
Message-ID:
<E.87WH7@xds13.ferranti.com>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rutgers!usc!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> <37256@nigel.ee.udel.edu> <20414:Nov2623:37:2390@kramden.acf.nyu.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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: <E.87WH7@xds13.ferranti.com> 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