Dynamic programmming complexity

#1

is top down approach is less efficent than bottom up approach with respect to time complexity
as in the case of KnackSack
bottom up–> O(items*capacity)
what will the memoization or top down complexity?

#2

Hey @sheikhhaji18
No they are same though there is some recursion overhead(extra time to make recursive calls save in stack etc) in top down approach

#3

Hey @sheikhhaji18
Also sometimes topdown is better than bottom up because no of distinct states are less
Here also its better

Se when u want o maximize N and u can break it to N/2+N/3+N/4 Here u are not using most of the states like N/2+1 to N-1 these are redundant to u
so in top down u wont calculate them but in bottum up u will

#4

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.