logoalt Hacker News

kadoban • today at 8:34 AM • 0 replies • view on HN

> Sure but 2^n space complexity to get O(1) time complexity works for all n even infinite.

That's just incorrect. Are you assuming the table starts pre-filled, and has O(1) lookup? Nobody is using a model like that for this problem.

2^n space complexity doesn't automatically mean you get to fill that space with 2^n chosen computed values for free.

There's models with "oracle"s for various sub-problems and such (that's essentially what you're describing as the ability you're baking in to your model of computation, it can look up the answer to any multiplication for free), but that's not an interesting model for this problem.

If you do that you're just asking "hey, how long does it take to multiply two numbers if multiplying two numbers is free". Boring question, and not the one anyone else is asking.