Comment by fooker

You can’t put everything in a lookup table with the lookup cost being O(1).

If the things you have to memoize are super-linear, suppose you need to store some value related to all subsets of an input set of size n.

There’s no way you can do this in O(1), even assuming infinitely large memory.