how to calculate the time complexity of dp problem with top down approach in the bottom up approach it is easily understandable but in top down it’s confused me…
Time complexity of top up
Upon every recursive calls, there are two possibilities, ie either pick the present first wine or present last wine! which gets to O(2^n)!, but with memoization, it becomes O(n^2) only which is number of distinct states!
for recursive how it is 2^n factorial it should be 2^n only…??
that was exclamation and not factorial!!!
so basically after making tree we have to check the states whic are traversed once only??
We skip those states which are already computed, hence our solution is optimized
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.