Hey there and welcome back!
In the previous videos we have discussed the first approach for solving the word break question, and
we have also returned the pseudo code for solving the question, which is what we have over here.
Now let's take a look at the space and time complexity of the approach that we came up with for this.
Let's say that n is the length of the given string, and m is the length of the word dictionary, or
the number of words in the word dictionary.
Now, when it comes to the space complexity of this approach, it's pretty straightforward.
It will be of the order of n square, because we have this DP array which is of the size n into n.
Now what about the time complexity?
So for that let's take a look at the pseudo code which we have over here.
Now we have nested for loops over here.
And this part the length taking values from one to n has approximately n operations.
And this part for I taking the values from zero to n minus l.
This has an upper bound of n okay.
So that's why if we combine these two for loops, the time complexity of this part of the solution is
of the order of n squared.
Now let's go deeper.
So over here we are checking whether the substring that goes from I to j is in the word dictionary.
Now forming this substring which goes from I to j takes up work.
And the upper bound for this will be of the order of n, because n is the maximum length of the given
string.
And again we're just concerned with the upper bound of the time complexity.
So this part is an O of n operation.
And to check whether this is in the word dictionary because the word dictionary has m words.
So checking whether this substring is in word dictionary is going to take work of the order of m okay.
Therefore, the total time complexity of this statement over here is of the order of n plus m.
So we have time complexity of the order of n plus M for executing this line of code.
And then we have the else part over here.
So k takes values from I up to j minus one okay.
And we are checking all the possible partitions.
And therefore this is an O of n operation.
Because again notice k is taking values from I to j minus one.
And this has an upper bound of the order of n, pretty much similar to how we found the upper bound
of this part to be of the order of n.
Okay, so now that we have the time complexities or the work required for the different parts of the
solution, let's try to identify what the total time complexity of the solution is.
Now if you take a look at these, this part over here, the time complexity of this part of the solution
is of the order of n plus m.
And over here we have already seen that the time complexity is of the order of n square, and therefore
the total time complexity of this approach is of the order of n squared into n plus m.