Comment by crest

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.