Comment by crest
11 hours ago
Than you modelled it incorrectly or n is small. A large lookup table is not O(1) in the real world as anyone who compares the access time of a register file, an L1 cache, and HBM3 (or DDR5) memory would realise. Even in a world of spherical cows in a vacuum lookup latency increases at least linearly with the radius of spherical volume the signal has to pass through.
However non-uniform your data access latencies are, algorithmic analysis treats all of them as O(1) as an axiom.
If you don't like that convention, you are free to use your own, but it is going to confuse people who use the standard convention. And the convention makes a lot of sense when you stop and think about the problem that people are trying to solve.