1
00:00:00,320 --> 00:00:02,270
Hey there and welcome back.

2
00:00:02,270 --> 00:00:09,350
Let's now take a look at the space and time complexity for the memoization approach that we came up

3
00:00:09,350 --> 00:00:09,800
with.

4
00:00:09,800 --> 00:00:17,180
So over here, notice that the space complexity is going to be of the order of n square because we have

5
00:00:17,180 --> 00:00:18,710
this 2D table.

6
00:00:18,710 --> 00:00:22,070
So the space complexity is of the order of n square.

7
00:00:22,130 --> 00:00:30,170
And the time complexity is also of the order of n square, because that's the upper bound or the maximum

8
00:00:30,170 --> 00:00:36,920
subproblems over here that we would have to calculate, because at max we would calculate n square places

9
00:00:36,920 --> 00:00:41,210
and then no more, because we calculate everything once and store it.

10
00:00:41,210 --> 00:00:49,100
And if we re-encounter a subproblem that was previously solved, and we see that the value of that subproblem

11
00:00:49,100 --> 00:00:54,980
in this table is not minus one, we would just take that value in constant time and return it.

12
00:00:54,980 --> 00:00:58,970
So that's why the time complexity is of the order of n square.

13
00:00:58,970 --> 00:01:01,910
And remember that this is the upper bound.

14
00:01:02,480 --> 00:01:10,100
Also take a note that we can do the memoization approach using a 1D array as well.

15
00:01:10,100 --> 00:01:17,120
But over here we have discussed the more intuitive approach where we are using a two dimensional array.

16
00:01:17,120 --> 00:01:24,500
When we discuss the bottom up or tabulation approach, we will discuss it both with a 2D approach as

17
00:01:24,500 --> 00:01:27,260
well as the approach where we can use a 1D array.

18
00:01:27,260 --> 00:01:29,420
So more of that in a future video.