I think, though, that your argument depends very directly on hardware implementation concerns, which is exactly the kind of thing that big O notation is meant to abstract away.
It doesn't. It merely depends on processing speed being finite. If you need to address the 2^(2^64)th item (remember, big O notation is about behavior as n goes to infinity), your item index needs 2^64 bits. You can't determine what item to get without looking at all the bits in the index. If your processing speed is finite, that requires time proportional to the number of bits in the index.
reply