1
00:00:00,080 --> 00:00:00,980
Welcome back.

2
00:00:00,980 --> 00:00:07,580
Let's now take a look at the space and time complexity for the memoization approach for solving the

3
00:00:07,580 --> 00:00:09,500
matrix chain multiplication question.

4
00:00:09,500 --> 00:00:16,460
Now, when it comes to the space complexity, it's going to be of the order of n square because of the

5
00:00:16,460 --> 00:00:19,370
2d dp array that we will be using.

6
00:00:19,370 --> 00:00:23,870
And again, remember we will also be using space on the recursive call stack.

7
00:00:23,870 --> 00:00:28,610
But the maximum depth of the recursive call stack will be of the order of n.

8
00:00:28,610 --> 00:00:33,710
And that's why the space complexity for the recursive solution was of the order of n okay.

9
00:00:33,710 --> 00:00:38,000
And between n square and n n square is much larger.

10
00:00:38,000 --> 00:00:42,950
And that's why the space complexity of this approach is of the order of N square.

11
00:00:42,950 --> 00:00:45,170
Now what about the time complexity?

12
00:00:45,170 --> 00:00:51,410
The time complexity of this approach is going to be of the order of n square into n.

13
00:00:51,410 --> 00:00:53,060
Now why is that the case?

14
00:00:53,060 --> 00:00:58,760
This is the case because there are n squared I comma j combinations okay.

15
00:00:58,760 --> 00:01:04,550
And for each I comma j combination, which is what each of these are about right.

16
00:01:04,550 --> 00:01:12,110
In the recursive tree for each I comma j combination, we'll have to do at most n operations because

17
00:01:12,110 --> 00:01:14,240
we have to try every partition, right.

18
00:01:14,240 --> 00:01:17,240
So k will take the value from I up to j minus one.

19
00:01:17,240 --> 00:01:19,490
And the upper bound for this is n.

20
00:01:19,490 --> 00:01:26,240
So for n square combinations we'll have to do at max n operations for each of these combinations.

21
00:01:26,240 --> 00:01:31,790
So that's why the total time complexity is of the order of n squared into n.

22
00:01:31,790 --> 00:01:35,330
Now why are there n square I comma j combinations?

23
00:01:35,330 --> 00:01:41,180
You can think of it in this manner that the number of subarrays that you can form from this array will

24
00:01:41,180 --> 00:01:42,530
be bounded by n squared.

25
00:01:42,530 --> 00:01:42,800
Right.

26
00:01:42,800 --> 00:01:44,660
So we have seen similar things previously.

27
00:01:44,660 --> 00:01:50,480
So the total time complexity for this approach is of the order of n cube.