Welcome back.
Let's now take a look at the space and time complexity for the memoization approach for solving the
matrix chain multiplication question.
Now, when it comes to the space complexity, it's going to be of the order of n square because of the
2d dp array that we will be using.
And again, remember we will also be using space on the recursive call stack.
But the maximum depth of the recursive call stack will be of the order of n.
And that's why the space complexity for the recursive solution was of the order of n okay.
And between n square and n n square is much larger.
And that's why the space complexity of this approach is of the order of N square.
Now what about the time complexity?
The time complexity of this approach is going to be of the order of n square into n.
Now why is that the case?
This is the case because there are n squared I comma j combinations okay.
And for each I comma j combination, which is what each of these are about right.
In the recursive tree for each I comma j combination, we'll have to do at most n operations because
we have to try every partition, right.
So k will take the value from I up to j minus one.
And the upper bound for this is n.
So for n square combinations we'll have to do at max n operations for each of these combinations.
So that's why the total time complexity is of the order of n squared into n.
Now why are there n square I comma j combinations?
You can think of it in this manner that the number of subarrays that you can form from this array will
be bounded by n squared.
Right.
So we have seen similar things previously.
So the total time complexity for this approach is of the order of n cube.