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.