3 ms·
The 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) -- i
by SamReidHughes 16y ago
The 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.