Let's now take a look at the space and time complexity of the space optimized tabulation approach.
Now, as we have discussed, we are just going to store two 1D arrays of size w.
So prev is going to be an array of size w.
And cr is going to be an array of size w.
So the space complexity is not of the order of n into W, as was the case previously.
But now the space complexity is just going to be of the order of W.
So notice that we have significantly improved the space complexity.
Now when it comes to the time complexity, it's still going to be of the order of N into W, because
we have to go through all of these cells and compute the values.
So the time complexity is still O of n into W, but the space complexity is of the order of W.
And these are the four approaches that we have discussed for solving the zero one knapsack problem.