News for hackers. Stuff that matters.
Re:Why databases use ordered indexes but programming uses ha... by dmurray on Monday December 09, 2019 @07:43PM (#21748453)
Constant-time arithmetic is realistic in most normal situations, like evaluating the performance of a hash table implementation. Perhaps your implementation uses 32 bits for the hash function, and can only scale to 4 billion slots. Maybe your implementation of a vector has the same limitation. In general, the reason you'll have trouble trying to store 2^trillion items is not because you chose a data structure with worse asymptotic performance than you expected, it's because you run out of space in the universe in which to store them.

So saying such a structure has O(1) asymptotic access time is not perfectly true in a mathematical sense, for unrealistic numbers. But it's certainly realistic.

Re:Why databases use ordered indexes but programming uses ha... by jhanschoo on Tuesday December 10, 2019 @02:18AM (#21750381)
Yes, it is, but the question is how do you make this notion of "realistic" formal and rigorous. The usual model for complexity analyses, the TM, can't do constant-time arithmetic. So we're interested in a more powerful model.

I'd proposed a model in a sibling comment that seems to be the one most people use for analyzing algorithms.

Re:Why databases use ordered indexes but programming uses ha... by johncolanduoni on Tuesday December 10, 2019 @04:40AM (#21751044)
A Turing machine can do constant-time arithmetric (or more simply, constant-time bound arithmetic) for operands of bounded size, as was suggested above.