1
00:00:00,140 --> 00:00:01,160
Welcome back.

2
00:00:01,160 --> 00:00:07,760
Let's now take a look at the space and time complexity for the tabulation approach for solving the matrix

3
00:00:07,760 --> 00:00:09,590
chain multiplication question.

4
00:00:09,980 --> 00:00:12,500
And we have discussed the approach in the previous video.

5
00:00:12,500 --> 00:00:17,720
Now when it comes to the space complexity, it's going to be of the order of n squared.

6
00:00:17,720 --> 00:00:19,400
And that's pretty straightforward.

7
00:00:19,400 --> 00:00:22,340
It's because we are using this 2D DP array.

8
00:00:22,370 --> 00:00:24,770
Now what about the time complexity?

9
00:00:24,770 --> 00:00:30,710
The time complexity of this approach is going to be of the order of n squared into n.

10
00:00:30,710 --> 00:00:32,360
Now why is this the case.

11
00:00:32,360 --> 00:00:40,070
Notice over here you have two parts n squared and n you have n squared over here because that's the

12
00:00:40,070 --> 00:00:45,830
upper bound of the number of cells that we will be iterating over in the DP array.

13
00:00:45,830 --> 00:00:46,310
Okay.

14
00:00:46,310 --> 00:00:51,080
Or it's the upper bound of the number of subarrays that we need to consider okay.

15
00:00:51,080 --> 00:00:53,210
So that's why we have n squared over here.

16
00:00:53,210 --> 00:00:58,370
And for each cell we'll have to do a maximum of n operations.

17
00:00:58,370 --> 00:01:02,570
Because of this part where k takes the values from I to j.

18
00:01:02,570 --> 00:01:05,420
And this has an upper bound of n okay.

19
00:01:05,420 --> 00:01:13,400
And that's why the upper bound of the time complexity is n squared into n, or the time complexity of

20
00:01:13,400 --> 00:01:16,130
this solution is of the order of n cube.