1
00:00:00,140 --> 00:00:06,470
Now, what about the space and time complexity for the one dimensional tabulation approach that we have

2
00:00:06,470 --> 00:00:08,690
come up with in the previous few videos?

3
00:00:08,690 --> 00:00:10,730
Let's discuss that in this video.

4
00:00:10,730 --> 00:00:16,610
Okay, so when it comes to the time complexity, notice over here we have a for loop.

5
00:00:16,610 --> 00:00:22,850
And this takes up work of the order of N because I goes from zero up to n minus one.

6
00:00:22,850 --> 00:00:25,310
And then we have another for loop over here.

7
00:00:25,310 --> 00:00:28,820
And let's say we have m words in the word dictionary.

8
00:00:28,820 --> 00:00:34,400
So as we have to go through, in the worst case through every word in our dictionary, this takes up

9
00:00:34,400 --> 00:00:36,230
work of the order of M.

10
00:00:36,410 --> 00:00:44,090
And over here we have to form a substring that starts at this particular index and goes up to index

11
00:00:44,090 --> 00:00:47,540
I and to form a substring from a string.

12
00:00:47,540 --> 00:00:52,100
It takes up work of the order of the length of the substring.

13
00:00:52,100 --> 00:01:00,620
And if we can generalize and say that k is the average length of words in the word dictionary, then

14
00:01:00,620 --> 00:01:05,300
this over here will take up work of the order of k, okay.

15
00:01:05,300 --> 00:01:11,780
And these are the three aspects of our solution that contribute to the time complexity.

16
00:01:11,780 --> 00:01:18,440
And because these are nested within each other like for example, for each value of I we have to do

17
00:01:18,440 --> 00:01:19,190
these checks.

18
00:01:19,190 --> 00:01:22,970
And for each word we'll have to form a substring.

19
00:01:22,970 --> 00:01:23,300
Right.

20
00:01:23,300 --> 00:01:25,220
So they are nested within each other.

21
00:01:25,220 --> 00:01:32,300
And that's why we can say that the time complexity of this approach is of the order of n into m into

22
00:01:32,300 --> 00:01:32,690
k.

23
00:01:32,810 --> 00:01:36,710
And when it comes to the space complexity, it's pretty straightforward.

24
00:01:36,710 --> 00:01:42,320
It's going to be of the order of n because we need this one dimensional DP array.

25
00:01:42,320 --> 00:01:46,610
So the time complexity is of the order of n into m into k.

26
00:01:46,610 --> 00:01:50,690
And the space complexity of this approach is of the order of n.