How does complexity get reduced to O(n^2) from O(2^n) in case of memoization?

Question

I am currently learning dynamic programming via memoization and tabularization technique. With reference to following link,(Longest increasing sequence problem), I didn't understand how the complexity is reduced to O(n^2) from O(2^n) when we memoize?

https://leetcode.com/problems/longest-increasing-subsequence/solution/

Answer 1

When memoizing a function, you make a note each time you call that function of a) the parameters and b) the result. Then next when you want to call the function again, you check in your notes whether you've called that function before with the parameters you want to use this time. If you have, you don't need to call the function again, because you already have the result. This way the function is called only as many times as you have distinct parameters: if you want to call it with parameters you've used already, you save having to call it.

This approach works well where a) the function is deterministic, i.e. returns the same value each time it is called with the same paramters, and b) the function is expensive compared to the cost of memoization.

The example you cite says this:

In the previous approach, many recursive calls had to made again and again with the same parameters. This redundancy can be eliminated by storing the results obtained for a particular call in a 2-d memorization array

Here the function in question is called O(2ⁿ) times, but with only O(n²) different sets of parameters. Using memoization, the function is called once only for each different parameter set (O(n²)) rather than each time the algorithm needs the answer (O(2ⁿ)).

Here is a reference which may help.