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

2
00:00:00,980 --> 00:00:07,070
Now let's discuss the space and time complexity for the recursive approach for solving the matrix chain

3
00:00:07,070 --> 00:00:08,480
multiplication question.

4
00:00:08,750 --> 00:00:15,920
Now when it comes to the space complexity, it's going to be of the order of n because the maximum depth

5
00:00:15,920 --> 00:00:19,310
of the recursive tree will be of the order of n.

6
00:00:19,310 --> 00:00:21,590
Now what about the time complexity?

7
00:00:21,620 --> 00:00:27,050
The time complexity of this approach will definitely be exponential in nature.

8
00:00:27,050 --> 00:00:32,150
Okay, because of the fact that we keep branching out, as you can see over here.

9
00:00:32,240 --> 00:00:34,280
And then we are not storing anything.

10
00:00:34,280 --> 00:00:36,320
We have not implemented memoization yet.

11
00:00:36,320 --> 00:00:36,710
Right.

12
00:00:36,710 --> 00:00:39,920
So that's why the time complexity will be exponential.

13
00:00:39,920 --> 00:00:46,910
And to be more accurate, it's going to be of the order of two to the power n into n, where n is the

14
00:00:46,910 --> 00:00:48,500
size of the input array.

15
00:00:48,500 --> 00:00:50,900
Now why is this the case over here?

16
00:00:50,900 --> 00:00:54,350
Notice we have two components two to the power n and n.

17
00:00:54,350 --> 00:01:00,800
Now we have two to the power n over here because that's the number of partitions that we can make okay.

18
00:01:00,800 --> 00:01:05,480
And you can refer the palindrome partitioning question where we have discussed this in detail.

19
00:01:05,480 --> 00:01:09,620
So we'll have partitions of the order of two to the power n.

20
00:01:09,620 --> 00:01:18,170
And for each partition notice that we have to use a variable k that iterates from I up to j minus one.

21
00:01:18,170 --> 00:01:25,280
Now this will have an upper bound of n, and that's why the total time complexity has an upper bound

22
00:01:25,280 --> 00:01:27,950
of two to the power n into n.