1
00:00:00,450 --> 00:00:02,310
Hey there and welcome back!

2
00:00:02,310 --> 00:00:08,550
In the previous videos we have discussed the first approach for solving the word break question, and

3
00:00:08,550 --> 00:00:13,620
we have also returned the pseudo code for solving the question, which is what we have over here.

4
00:00:13,620 --> 00:00:20,010
Now let's take a look at the space and time complexity of the approach that we came up with for this.

5
00:00:20,010 --> 00:00:27,810
Let's say that n is the length of the given string, and m is the length of the word dictionary, or

6
00:00:27,810 --> 00:00:30,180
the number of words in the word dictionary.

7
00:00:30,180 --> 00:00:35,940
Now, when it comes to the space complexity of this approach, it's pretty straightforward.

8
00:00:35,940 --> 00:00:42,990
It will be of the order of n square, because we have this DP array which is of the size n into n.

9
00:00:42,990 --> 00:00:45,270
Now what about the time complexity?

10
00:00:45,270 --> 00:00:49,170
So for that let's take a look at the pseudo code which we have over here.

11
00:00:49,170 --> 00:00:51,990
Now we have nested for loops over here.

12
00:00:51,990 --> 00:00:58,950
And this part the length taking values from one to n has approximately n operations.

13
00:00:58,950 --> 00:01:03,510
And this part for I taking the values from zero to n minus l.

14
00:01:03,540 --> 00:01:06,420
This has an upper bound of n okay.

15
00:01:06,420 --> 00:01:12,990
So that's why if we combine these two for loops, the time complexity of this part of the solution is

16
00:01:12,990 --> 00:01:14,850
of the order of n squared.

17
00:01:15,000 --> 00:01:16,860
Now let's go deeper.

18
00:01:16,860 --> 00:01:23,250
So over here we are checking whether the substring that goes from I to j is in the word dictionary.

19
00:01:23,250 --> 00:01:27,630
Now forming this substring which goes from I to j takes up work.

20
00:01:27,630 --> 00:01:34,290
And the upper bound for this will be of the order of n, because n is the maximum length of the given

21
00:01:34,290 --> 00:01:34,680
string.

22
00:01:34,680 --> 00:01:38,220
And again we're just concerned with the upper bound of the time complexity.

23
00:01:38,220 --> 00:01:41,160
So this part is an O of n operation.

24
00:01:41,160 --> 00:01:47,190
And to check whether this is in the word dictionary because the word dictionary has m words.

25
00:01:47,190 --> 00:01:54,090
So checking whether this substring is in word dictionary is going to take work of the order of m okay.

26
00:01:54,090 --> 00:02:01,980
Therefore, the total time complexity of this statement over here is of the order of n plus m.

27
00:02:02,310 --> 00:02:08,340
So we have time complexity of the order of n plus M for executing this line of code.

28
00:02:08,340 --> 00:02:10,320
And then we have the else part over here.

29
00:02:10,320 --> 00:02:14,280
So k takes values from I up to j minus one okay.

30
00:02:14,280 --> 00:02:17,190
And we are checking all the possible partitions.

31
00:02:17,190 --> 00:02:20,190
And therefore this is an O of n operation.

32
00:02:20,190 --> 00:02:24,000
Because again notice k is taking values from I to j minus one.

33
00:02:24,000 --> 00:02:29,400
And this has an upper bound of the order of n, pretty much similar to how we found the upper bound

34
00:02:29,400 --> 00:02:31,980
of this part to be of the order of n.

35
00:02:31,980 --> 00:02:38,160
Okay, so now that we have the time complexities or the work required for the different parts of the

36
00:02:38,160 --> 00:02:43,770
solution, let's try to identify what the total time complexity of the solution is.

37
00:02:43,770 --> 00:02:49,920
Now if you take a look at these, this part over here, the time complexity of this part of the solution

38
00:02:49,920 --> 00:02:52,140
is of the order of n plus m.

39
00:02:52,140 --> 00:02:58,620
And over here we have already seen that the time complexity is of the order of n square, and therefore

40
00:02:58,620 --> 00:03:05,100
the total time complexity of this approach is of the order of n squared into n plus m.