1
00:00:00,230 --> 00:00:01,370
Welcome back.

2
00:00:01,370 --> 00:00:09,140
In the previous video we have discussed and we have taken a look at how the algorithm would fill the

3
00:00:09,140 --> 00:00:14,720
table for finding the answer for the last question where we used a 2D array.

4
00:00:14,960 --> 00:00:20,720
Now let's take a look at the space and time complexity of the approach that we came up with.

5
00:00:20,750 --> 00:00:27,050
Now, the space complexity over here is going to be of the order of n square, because we need this

6
00:00:27,050 --> 00:00:28,340
2D dp array.

7
00:00:28,790 --> 00:00:34,580
And then the time complexity is also going to be of the order of n square, because this is the upper

8
00:00:34,580 --> 00:00:40,700
bound or the maximum number of operations that we need when we iterate through the elements.

9
00:00:40,700 --> 00:00:43,010
Now it's going to be less than n square.

10
00:00:43,010 --> 00:00:45,320
But then we just need the upper bound right.

11
00:00:45,320 --> 00:00:48,230
So over here we had three, then we have two.

12
00:00:48,260 --> 00:00:49,070
Then we have one right.

13
00:00:49,070 --> 00:00:52,940
So this is like something like one plus two plus three etc..

14
00:00:52,940 --> 00:00:59,600
You go up to n where n is the length of the array which is given to us.

15
00:00:59,600 --> 00:01:05,750
Now we know that this over here is of the order of n square, and that's why the time complexity of

16
00:01:05,750 --> 00:01:08,450
this solution is of the order of n square.