Hey there and welcome back.
Let's now take a look at the space and time complexity for the memoization approach that we came up
with.
So over here, notice that the space complexity is going to be of the order of n square because we have
this 2D table.
So the space complexity is of the order of n square.
And the time complexity is also of the order of n square, because that's the upper bound or the maximum
subproblems over here that we would have to calculate, because at max we would calculate n square places
and then no more, because we calculate everything once and store it.
And if we re-encounter a subproblem that was previously solved, and we see that the value of that subproblem
in this table is not minus one, we would just take that value in constant time and return it.
So that's why the time complexity is of the order of n square.
And remember that this is the upper bound.
Also take a note that we can do the memoization approach using a 1D array as well.
But over here we have discussed the more intuitive approach where we are using a two dimensional array.
When we discuss the bottom up or tabulation approach, we will discuss it both with a 2D approach as
well as the approach where we can use a 1D array.
So more of that in a future video.