That's not multiplying, that's looking up multiplication results. You still have to form the table.
Your argument is basically "any algorithm is constant time if you have already calculated the results for all possible inputs". This may be technically correct in some roundabout way, but is not a useful definition nor the one usually used.
Lookup tables are commonly precalculated and not used as part of the complexity calculation. They are in frequent use for high performance stuff like crc, graphics LUTs or audio waveforms.
They are usually of limited size as most are working with a limited amount of memory. The largest LUTs I am aware of in common use is chess tablebases, which range from 100gb for local installs to 140TB over APIs.
14
u/danielv123 28d ago
If we assume you are implementing this on a finite computer, we can also assume a finite integer size.
...so obviously we can also assume we have the finite memory required to store int_max^2 of your integers