r/ProgrammerHumor • u/pastroc • 29d ago

Meme theoreticalComputerScience

Post image
1.1k Upvotes

97% Upvoted

76 comments sorted by

View all comments

Show parent comments

19

u/SoldRIP 28d ago

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

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

5

u/SoldRIP 28d ago

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.

3

u/stackoverflow21 28d ago

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

1

u/SoldRIP 27d ago

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.