Welcome back.
Now let's discuss the space and time complexity for the recursive 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 because the maximum depth
of the recursive tree will be of the order of n.
Now what about the time complexity?
The time complexity of this approach will definitely be exponential in nature.
Okay, because of the fact that we keep branching out, as you can see over here.
And then we are not storing anything.
We have not implemented memoization yet.
Right.
So that's why the time complexity will be exponential.
And to be more accurate, it's going to be of the order of two to the power n into n, where n is the
size of the input array.
Now why is this the case over here?
Notice we have two components two to the power n and n.
Now we have two to the power n over here because that's the number of partitions that we can make okay.
And you can refer the palindrome partitioning question where we have discussed this in detail.
So we'll have partitions of the order of two to the power n.
And for each partition notice that we have to use a variable k that iterates from I up to j minus one.
Now this will have an upper bound of n, and that's why the total time complexity has an upper bound
of two to the power n into n.