|
|
|
|
|
|
by Cushman
4005 days ago
|
|
|
> Where? Every treatment I've seen takes arithmetic as linear in the number of bits. [1] This is still consistent with O(n log n) for sorts because you can assume a bound on element size, and still only have constant factor overhead. This is probably the only point of disagreement here. If I understand your critique of the O(1) result, it's that addressing n elements takes arithmetic (hashing) on numbers of log n bits. ISTM that, assuming an integer RAM model, that same critique must apply to any input. A mere pointer into an array of n elements has log n bits, so just incrementing and testing the pointer can't be O(1), and even iterating that array can't be O(n). It's still hard for me to see any reason why the one or two arithmetic operations in a for loop can be O(1), while the larger but still constant number used by a hash function can't. |
|
|
It's not the addressing I object to -- this whole domain consistently assumes O(1) seek times. It's the computation of the hash itself. A hash function that, by supposition, minimizes collisions is going to have to avalanche the whole thing such that it has to perform a complex calculation -- not mere lookup -- that incorporates multiple combinations of the elements. The growth in cost is not from doing seeks over bigger ranges but from computation. You can no more assume away that growth than you can assume that md5 is just as expensive than SHA256.
>ISTM that, assuming an integer RAM model, that same critique must apply to any input. A mere pointer into an array of n elements has log n bits, so just incrementing and testing the pointer can't be O(1), and even iterating that array can't be O(n).
I never objected to this before but I've always disagreed: iterating needn't be log(n) because any such procedure can be optimized away to get the next element via either a) a seek, or b) incremeting a value, which is constant amortized (because bit rollover is exponentially rare).