[sfink]

It doesn't change the time complexity. Both are O(n). Your point about convenience stands, though.

Actually, if you go into fully pedantic mode, the set version is worse. Hash-based set insertion is commonly taken to be O(1), but that depends on hash comparison being O(1), which depends on using single-word hash values, which means your n is bounded by eg 2^63 (50% occupancy) or whatever. Honestly fine in practice, but hash lookup isn't "as" O(1) as indexing into an array. (ie, it requires a less realistic cost model.)

You also need your keys' length to be bounded by a constant. Otherwise just hashing everything will exceed O(n).

[orlp]

O(1) indexing into an array is a much bigger lie in practice than relying on single-word hash values. It breaks down much, much sooner which is why we have multiple levels of caches to try and hide this.

In reality random indexing is O(sqrt(n)) for 2D memory chips, and at best O(cbrt(n)) in our 3D physical world.

[Joker_vD]

And adding two numbers is also O(m+n) where m, n is their length in bits, sure.