Welcome back.
In the previous video we have discussed and we have taken a look at how the algorithm would fill the
table for finding the answer for the last question where we used a 2D array.
Now let's take a look at the space and time complexity of the approach that we came up with.
Now, the space complexity over here is going to be of the order of n square, because we need this
2D dp array.
And then the time complexity is also going to be of the order of n square, because this is the upper
bound or the maximum number of operations that we need when we iterate through the elements.
Now it's going to be less than n square.
But then we just need the upper bound right.
So over here we had three, then we have two.
Then we have one right.
So this is like something like one plus two plus three etc..
You go up to n where n is the length of the array which is given to us.
Now we know that this over here is of the order of n square, and that's why the time complexity of
this solution is of the order of n square.