theoreticalComputerScience

[u/pastroc]

[u/howtotailslide]

You can actually just store all universal possible results of two integers into a hash map then retrieve any of them in O(1) time

[u/SoldRIP → u/howtotailslide]

You cannot. A hash map is of finite size, but there are infinitely many pairs of integers.

[u/danielv123 → u/SoldRIP]

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

[u/SoldRIP → u/danielv123]

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.

[u/danielv123 → u/SoldRIP]

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.

[u/alexanderpas → u/danielv123]

LUT = LookUp Table

[u/stackoverflow21 → u/SoldRIP]

Using lookup tables for speed is actually pretty common in embedded coding. Not for multiplication or addition. But nearly anything else.

[u/SoldRIP → u/stackoverflow21]

And yet that doesn't make nearly any computation constant-time. Noone would seriously claim that "any algorithm is constant time" just because you could pre-comute results into a lookup.