Welcome back.
Let's now discuss the space and time complexity of the approach, which we just now discussed for solving
the Elias question over here.
Notice that we are going through all the elements in the array which is given to us.
So that's n operations.
And for each element in the worst case we would have to do log n operations to identify the index where
it has to be inserted in the subsequence that we are building.
So the worst case time complexity or the upper bound is going to be of the order of n into log n n,
because we are iterating through all the elements and log n for doing binary search for each of these
elements, which would need to be done in the worst case scenario.
So the time complexity is going to be of the order of n into log n, and the space complexity of this
solution is going to be of the order of n, because we have to build the subsequence, and this will
take space maximum of the order of n if we can include all the elements, like.
For example, if the array given to us is one, two, three, the subsequence ultimately will be one,
two, three.
So this is going to take space of the order of n.