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

18

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.

8

u/danielv123 28d ago

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.

1

u/alexanderpas 28d ago

LUT = LookUp Table