4 ms·
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 hi
by continuational 7y ago
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 7y agoThis kind of pedantry doesn't add anything to the discussion. We all know big-O notation is a theoretical abstraction.
- continuational 7y agoI 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.