gvcormack@watmum.UUCP (03/01/87)
When you start arguing about memory addresses consuming log(n) space
and hence log(n) time to manipulate, you are starting to attack the
unit-cost RAM model of computation that is commonly assumed in
computing the time and space requirements of algorithms.
It is fine to attack this model, but let's not apply a double
standard. Comparison sorting requires n log n COMPARISONS. If
you assume a logarithmic cost model, I think it is fair to say
that comparing two keys of length log n requires log n time, and
therefore that comparison sorting requires OMEGA(n log n log n) time.
Radix sort does O(n) operations (not comparisons) on keys. If you
assume keys can be manipulated in unit time, you get O(n) sorting.
If you assume logarithmic cost, you get O(n log n), but are still
better off than comparison sorting by a factor of log n!
Of course, for any n that you are likely to run into in your lifetime,
you can find k such that k > log(n), and the practical significance
of this entire argument disappears. Be conservative, though -- a
while back a very large computer manufacturer thought k=24 was
adequate. Now, many believe k=32 does the trick...
--
Gordon V. Cormack CS Dept, University of Waterloo, Canada N2L 3G1
gvcormack@mum.waterloo { .CSNET or .CDN }
gvcormack@water { UUCP or BITNET }