Let's now discuss the space and time complexity of the memoization approach for the zero one knapsack
problem.
The space complexity is evident.
It's going to be of the order of N into W, because we have to create and store this 2D array.
So this array over here has w columns.
So the columns are over here.
And then you have n rows.
So that's why the space complexity is of the order of n into w.
And the time complexity is also going to be of the order of n into W, because that's the maximum or
the upper bound of the number of computations that we would have to do, because we're just doing every
computation once.
And the maximum possible subproblems that there can be is of the order of n into W.
So the time complexity is also of the order of n into W.
Now do remember the memoization approach is still a recursive approach and therefore in some rare cases
where we are dealing with high values or large values, we still have the risk of encountering a stack
overflow error.
So that's where the tabulation approach becomes very handy.
And let's discuss that in the next video.