[dan-robertson]

This argument does not apply to the OP as it does not account for any bookkeeping. I think an actual answer is more complicated and will entirely depend on the definition of “random access pattern.”

[carlmr]

Yes, and bookkeeping and randomness both cost something.