I think this way of looking at the problem is misleading. O(1) or O(N) always stays O(1) or O(N), just the constant changes. You can always access any element i

I think this way of looking at the problem is misleading. O(1) or O(N) always stays O(1) or O(N), just the constant changes. You can always access any element in RAM (on a SSD, HDD) in a bounded amount of time. Use that pessimistic time as the time of one step. Viewed in this way, O(N) is still O(N), and a processor with caches is a magic device that somehow computes faster than O(N)... or for O(1) computes in sub-constant time (if that can be even well-defined).