4 ms·

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 ha

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.

lostmsu 7y ago
Same applies to trees thought: you have to multiply log n by that bit number, because each naive comparison will take O(bit number)
dmurray 7y ago
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.
- jhanschoo 7y ago
  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.
  - johncolanduoni 7y ago
    A Turing machine can do constant-time arithmetric (or more simply, constant-time bound arithmetic) for operands of bounded size, as was suggested above.
denormalfloat 7y ago
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.
- Kranar 7y ago
  >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)).
  - davedx 7y ago
    > 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))
jhanschoo 7y ago
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.

lostmsu 7y ago

Same applies to trees thought: you have to multiply log n by that bit number, because each naive comparison will take O(bit number)

dmurray 7y ago

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.

jhanschoo 7y ago
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.
- johncolanduoni 7y ago
  A Turing machine can do constant-time arithmetric (or more simply, constant-time bound arithmetic) for operands of bounded size, as was suggested above.

denormalfloat 7y ago

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.

Kranar 7y ago
>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)).
- davedx 7y ago
  > 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))

jhanschoo 7y ago

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.