Comment by _alternator_

Yes, but writing down the address in the lookup table takes log(2^n)=n bits, so the claim of an O(1) lower bound is simply wrong.