Now, what about the space and time complexity for the one dimensional tabulation approach that we have
come up with in the previous few videos?
Let's discuss that in this video.
Okay, so when it comes to the time complexity, notice over here we have a for loop.
And this takes up work of the order of N because I goes from zero up to n minus one.
And then we have another for loop over here.
And let's say we have m words in the word dictionary.
So as we have to go through, in the worst case through every word in our dictionary, this takes up
work of the order of M.
And over here we have to form a substring that starts at this particular index and goes up to index
I and to form a substring from a string.
It takes up work of the order of the length of the substring.
And if we can generalize and say that k is the average length of words in the word dictionary, then
this over here will take up work of the order of k, okay.
And these are the three aspects of our solution that contribute to the time complexity.
And because these are nested within each other like for example, for each value of I we have to do
these checks.
And for each word we'll have to form a substring.
Right.
So they are nested within each other.
And that's why we can say that the time complexity of this approach is of the order of n into m into
k.
And when it comes to the space complexity, it's pretty straightforward.
It's going to be of the order of n because we need this one dimensional DP array.
So the time complexity is of the order of n into m into k.
And the space complexity of this approach is of the order of n.