Constant-time arithmetic is realistic in most normal situations, like evaluating the performance of a hash table implementation. Perhaps your implementation use

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.