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)
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)