Never infinite if you have bounds on integer size. For n bits of input it's always possible to have a 2^n space complexity lookup table that's O(1) speed since 2^n covers all possibilities of n bits.

You don't need to go to these extremes regardless though. For small speedups take an nlogn algorithm and just move a very small part of the inner portion out in a similar tradeoff. Eg. "Every nth input is now part of a lookup." If you look at the openAIs <nlogn results there was a series of small improvements of this type (we take this part out, precomputing it, and likewise with this part and that small portion, aha! <nlogn!). I finally loaded the link above and it's 262million lines of such tricks in fact.

I think the thing non-mathematicians and non-CS people who only know complexity theory vaguely need to remember is that complexity theory has nothing to do with reality.

A 2^64bits lookup table only has O(1) lookup if you ignore the impossibility of creating a machine that has 2 exabytes of storage where all those bytes have the same access time. Or you'd have to redefine O(1) to be “at most the worst case”. But strictly speaking from the mathematical definition it’s O(1). Which is why no one in practical engineering takes most complexity results seriously as the entire field maps to practice poorly precisely for these reasons (all our machines use fixed integer math and have limited tape storage)

The whole point of this problem is that there are no bounds on integer size.

The whole point of complexity theory is that there are no bounds on input size.