[continuational]

In reality, array lookup is not O(1). It's orders of magnitude faster to do random lookups in an array that fits in L1 cache than one that doesn't. The cache hierachy makes array lookups O(log(n)) or possibly even O(sqrt(n)).

[dvt]

This kind of pedantry doesn't add anything to the discussion. We all know big-O notation is a theoretical abstraction.

[continuational]

I think you overestimate the number of programmers that know this. In my experience, < 50% of programmers know that random array lookups are not constant time in practice.

I mean they would be able to deduce it, but they just never made the connection.