Welcome back.
Let's now take a look at the space and time complexity for the tabulation approach for solving the matrix
chain multiplication question.
And we have discussed the approach in the previous video.
Now when it comes to the space complexity, it's going to be of the order of n squared.
And that's pretty straightforward.
It's because we are using this 2D DP array.
Now what about the time complexity?
The time complexity of this approach is going to be of the order of n squared into n.
Now why is this the case.
Notice over here you have two parts n squared and n you have n squared over here because that's the
upper bound of the number of cells that we will be iterating over in the DP array.
Okay.
Or it's the upper bound of the number of subarrays that we need to consider okay.
So that's why we have n squared over here.
And for each cell we'll have to do a maximum of n operations.
Because of this part where k takes the values from I to j.
And this has an upper bound of n okay.
And that's why the upper bound of the time complexity is n squared into n, or the time complexity of
this solution is of the order of n cube.