Welcome back.
Let's now discuss the space and time complexity for the approach that we have discussed in the previous
video.
The time complexity for this approach is going to be of the order of n squared, where n is the number
of elements in the array which is given to us.
Now why is that the case?
Let's think of what are the different aspects which contribute to the time complexity of this approach.
As we have discussed, we first need to sort the array which is given to us.
And if this array over here has n elements, sorting this array will take work of the order of n log
n.
The other aspect that takes up work over here is the nested for loop, which we will need to move the
I and j pointers.
Now, in the nested for loop, we know that I goes from one up to n minus one, and j goes from zero
to I minus one for each instance of I.
Now an upper bound for this nested for loop will be of the order of n square.
Okay.
So again this can be said as approximately n operations.
And over here also the upper bound for this would be n operations.
So that's why the upper bound for the nested for loop is of the order of n square.
And between n square and n log n n square is greater.
And that's why the time complexity of this approach is of the order of n squared.
Now what about the space complexity?
The space complexity of this solution is going to be of the order of n.
Now why is that the case?
Or let's think of what are the aspects that take up auxiliary space in this solution.
Now in this solution, the only thing that takes up extra space is the 1d dp array, which we have used
over here.
And as you can see over here, it has n elements or it can store n elements.
And that's why we are taking up space of the order of n for creating this DP array.
So the time complexity is of the order of n square, and the space complexity is of the order of n.