3 ms·
You don't need to compare all the bits in a word -- you just need to find the first place where two values differ.
by cperciva 16y ago
You 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.