4 ms·
If you are going to say that there really are log n bits in a word, then you also need to account for the time it takes to actually do a comparison, which would
by ssp 16y ago
If you are going to say that there really are log n bits in a word, then you also need to account for the time it takes to actually do a comparison, which would be Omega(log n) in the worst case because you can't describe n values with less than log n bits -- making comparison sort Omega (n log^2 n)
- cperciva 16y agoYou don't need to compare all the bits in a word -- you just need to find the first place where two values differ.
- ssp 16y agoIt isn't obvious to me that that is enough to guarantee amortized constant time.
- SamReidHughes 16y agoThe length of the common prefix generally grows linearly from 1 to O(log(n)) on randomly distributed values (and worse on less-randomly distributed values) -- if you follow a given value, it starts off being compared against another random value, then against a value with probably one bit in common, then against a value with probably two bits in common, and so on, until O(log(n)) comparisons have been done.