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

2
00:00:01,160 --> 00:00:07,700
Let's now take a look at the space and time complexity for the memoization approach that we have discussed

3
00:00:07,700 --> 00:00:09,260
in the previous videos.

4
00:00:09,290 --> 00:00:09,740
Okay.

5
00:00:09,740 --> 00:00:11,900
And we have the pseudocode over here.

6
00:00:11,900 --> 00:00:15,680
So this will make it very easy to take a look at the complexity analysis.

7
00:00:15,710 --> 00:00:21,020
Now when it comes to the space complexity it's going to be of the order of n.

8
00:00:21,020 --> 00:00:26,630
And there are two factors or two contributing factors towards the space complexity.

9
00:00:26,630 --> 00:00:33,410
The first is the recursive call stack, and the second is the DP array that we need for the memoization

10
00:00:33,410 --> 00:00:33,980
approach.

11
00:00:33,980 --> 00:00:34,430
Okay.

12
00:00:34,430 --> 00:00:39,470
And both of these have a space complexity of the order of n.

13
00:00:39,470 --> 00:00:42,200
Now for the DP array it's pretty straightforward.

14
00:00:42,200 --> 00:00:48,440
We have seen that if the length of the given string is n, then we will have n cells in the DP array,

15
00:00:48,440 --> 00:00:51,890
which is a one dimensional array for the approach that we have discussed.

16
00:00:51,890 --> 00:00:58,880
Now, when it comes to the recursive call stack, the maximum depth is going to be of the order of n,

17
00:00:58,880 --> 00:01:05,990
and to visualize this, just think of the scenario where the word dictionary has words of one character,

18
00:01:05,990 --> 00:01:06,470
okay?

19
00:01:07,740 --> 00:01:11,160
And let's say the string over here is given.

20
00:01:11,160 --> 00:01:14,580
And then we are going backwards one character at a time.

21
00:01:14,580 --> 00:01:21,150
So if this is the case, the maximum depth of the recursive call stack will be of the order of n.

22
00:01:21,150 --> 00:01:23,760
And again we're just trying to find an upper bound.

23
00:01:23,760 --> 00:01:30,900
And that's why for these two reasons, the space complexity of this approach, which is the memoization

24
00:01:30,900 --> 00:01:34,500
approach for solving this question, is of the order of n.

25
00:01:34,770 --> 00:01:37,140
Now what about the time complexity?

26
00:01:37,200 --> 00:01:42,780
Now for that, let's take a look at the various components in the solution that we have written or the

27
00:01:42,780 --> 00:01:44,430
pseudocode that we have written over here.

28
00:01:44,430 --> 00:01:51,630
Now, for the same reason for which we previously discussed that the maximum depth of the recursion

29
00:01:51,630 --> 00:01:56,820
tree, or the space used on the recursive call stack, is of the order of n.

30
00:01:56,820 --> 00:02:04,470
For the same reason, we can say that the check function over here will be called a maximum of n times.

31
00:02:04,470 --> 00:02:08,910
Okay, so the maximum times this function can be called is n times.

32
00:02:08,910 --> 00:02:13,140
So that takes up time of the order of n again.

33
00:02:13,140 --> 00:02:13,620
Why is that?

34
00:02:13,620 --> 00:02:20,730
So think of the case where you have one characters in the word, and then you will be calling the function

35
00:02:20,730 --> 00:02:24,810
n times to go through all the characters in the string which is given to you.

36
00:02:24,810 --> 00:02:30,540
So the upper bound, or the maximum number of times this function will be called is of the order of

37
00:02:30,540 --> 00:02:31,050
n.

38
00:02:31,050 --> 00:02:35,280
Now what about the different things that we're doing inside the body of the function.

39
00:02:35,280 --> 00:02:39,870
So over here notice we are going through every word in the word dictionary.

40
00:02:39,870 --> 00:02:47,340
And if there are m words in the word dictionary this would take up time of the order of m okay.

41
00:02:47,340 --> 00:02:52,740
And let's say the average length of the words in the word dictionary is equal to k.

42
00:02:52,860 --> 00:02:59,130
And if that is the case, then this part over here where we have to form a substring that starts at

43
00:02:59,130 --> 00:03:01,830
a particular index and goes up to a particular index.

44
00:03:01,830 --> 00:03:02,130
Okay.

45
00:03:02,130 --> 00:03:06,660
So that would take up work of the order of the length of this particular substring.

46
00:03:06,660 --> 00:03:12,420
But if we say that the average length of the substring that can be formed over here is equal to k,

47
00:03:12,450 --> 00:03:16,800
then we are doing work over here of the order of k okay.

48
00:03:16,800 --> 00:03:22,380
So these are the three components that contribute to the time complexity of this solution.

49
00:03:22,380 --> 00:03:30,570
And that's why the time complexity of this solution is going to be of the order of n into m into k okay.

50
00:03:30,570 --> 00:03:33,630
Because notice this n is in the outer layer.

51
00:03:33,630 --> 00:03:39,270
And then within each of these calls you have to do M operations over here.

52
00:03:39,270 --> 00:03:42,660
And within each M operation over here within it.

53
00:03:42,660 --> 00:03:42,900
Right.

54
00:03:42,900 --> 00:03:45,270
You have to do work of the order of K.

55
00:03:45,270 --> 00:03:50,460
So that's why the time complexity is of the order of n into m into k.