[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.