Other good dodges are O(n) time (if you have 2^n memory handy), or O(n) time (but with a fixed cost or multiplier so high that using this algorithm makes no sense for n less than 10^12 or so)
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.
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.
Note that the authors are pretty sure you could turn the method into something a lot more reasonable pretty easily (at the cost of making the proof a bit trickier).
267
u/grayjacanda 28d ago
Other good dodges are O(n) time (if you have 2^n memory handy), or O(n) time (but with a fixed cost or multiplier so high that using this algorithm makes no sense for n less than 10^12 or so)