News for hackers. Stuff that matters.
Re:Why databases use ordered indexes but programming uses ha... by Darmani on Monday December 09, 2019 @07:18PM (#21748267)
In some senses, no hash tables are O(1).

Hash tables are bounded below by the speed of arithmetic. A trillion-bit number takes a while to multiply. You may have never touched a trillion-bit number, but it's called "asymptotic" for a reason.

You only get O(1) if you use a model of computation in which arithmetic is constant time. It's simple to work with, even though it's not realistic, and opens up scenarios where you can encode a really complex operation into adding/multiplying some huge numbers, and then claim the overall computation is still fast.

Some theorists use a model of computation in which, if your input size n, then multiplying a log-n bit number is O(1), but multiplying an n-bit number is O(n). I have no idea how this is well-defined.

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.
Re:Why databases use ordered indexes but programming uses ha... by lostmsu on Monday December 09, 2019 @07:35PM (#21748396)
Same applies to trees thought: you have to multiply log n by that bit number, because each naive comparison will take O(bit number)
Re:Why databases use ordered indexes but programming uses ha... by jhanschoo on Tuesday December 10, 2019 @02:13AM (#21750364)
Indeed, in the TM model hash table lookups are necessarily Omega(n) in the length of data stored.

The model of computation used in these analyses and interview questions I'd say is a random-access infinite register machine of infinite size (and constant arithmetic), which is more powerful than a TM (and siblings) in complexity analyses.

Of course, they are useless for analyzing complexity classes of computational problems, but you can use them to talk about the complexity of computer algorithms.

Re:Why databases use ordered indexes but programming uses ha... by denormalfloat on Monday December 09, 2019 @11:48PM (#21749681)
That's not what big O notation is about. It represents the growth rate. In a the case of a hash table, the size of the thing you are hashing is not affected by the number of items present in the hash table. Putting a trillion bit integer into a hash table of other integers is still O(1); it's a constant.
Re:Why databases use ordered indexes but programming uses ha... by Kranar on Tuesday December 10, 2019 @12:15AM (#21749801)
>In a the case of a hash table, the size of the thing you are hashing is not affected by the number of items present in the hash table.

But it is, and that's precisely the reason why hash tables are not O(1) but rather O(log(n)). By the pigeon hole principle, it is impossible to store N items in a hash table using a key whose representation is less than log(N) bits without a collision. This means that there is a relationship between the the size of the key being hashed and the number of elements being inserted in the hash map, specifically the relationship is an element of O(log(n)).

Re:Why databases use ordered indexes but programming uses ha... by davedx on Tuesday December 10, 2019 @02:02AM (#21750321)
> But it is, and that's precisely the reason why hash tables are not O(1) but rather O(log(n))

I'm sorry, but as a reader it is quite amusing that various posters are claiming (all without citing any sources) hashtables are O(1), O(n) and O(log(n))