Welcome back.
Let's now take a look at the space and time complexity for the memoization approach that we have discussed
in the previous videos.
Okay.
And we have the pseudocode over here.
So this will make it very easy to take a look at the complexity analysis.
Now when it comes to the space complexity it's going to be of the order of n.
And there are two factors or two contributing factors towards the space complexity.
The first is the recursive call stack, and the second is the DP array that we need for the memoization
approach.
Okay.
And both of these have a space complexity of the order of n.
Now for the DP array it's pretty straightforward.
We have seen that if the length of the given string is n, then we will have n cells in the DP array,
which is a one dimensional array for the approach that we have discussed.
Now, when it comes to the recursive call stack, the maximum depth is going to be of the order of n,
and to visualize this, just think of the scenario where the word dictionary has words of one character,
okay?
And let's say the string over here is given.
And then we are going backwards one character at a time.
So if this is the case, the maximum depth of the recursive call stack will be of the order of n.
And again we're just trying to find an upper bound.
And that's why for these two reasons, the space complexity of this approach, which is the memoization
approach for solving this question, is of the order of n.
Now what about the time complexity?
Now for that, let's take a look at the various components in the solution that we have written or the
pseudocode that we have written over here.
Now, for the same reason for which we previously discussed that the maximum depth of the recursion
tree, or the space used on the recursive call stack, is of the order of n.
For the same reason, we can say that the check function over here will be called a maximum of n times.
Okay, so the maximum times this function can be called is n times.
So that takes up time of the order of n again.
Why is that?
So think of the case where you have one characters in the word, and then you will be calling the function
n times to go through all the characters in the string which is given to you.
So the upper bound, or the maximum number of times this function will be called is of the order of
n.
Now what about the different things that we're doing inside the body of the function.
So over here notice we are going through every word in the word dictionary.
And if there are m words in the word dictionary this would take up time of the order of m okay.
And let's say the average length of the words in the word dictionary is equal to k.
And if that is the case, then this part over here where we have to form a substring that starts at
a particular index and goes up to a particular index.
Okay.
So that would take up work of the order of the length of this particular substring.
But if we say that the average length of the substring that can be formed over here is equal to k,
then we are doing work over here of the order of k okay.
So these are the three components that contribute to the time complexity of this solution.
And that's why the time complexity of this solution is going to be of the order of n into m into k okay.
Because notice this n is in the outer layer.
And then within each of these calls you have to do M operations over here.
And within each M operation over here within it.
Right.
You have to do work of the order of K.
So that's why the time complexity is of the order of n into m into k.