Hey there and welcome back.
So we have discussed the greedy algorithm that we can use to solve the two city scheduling question.
Now let's go ahead and discuss the space and time complexity of the approach that we came up with.
Now in the previous video, we have discussed that these are the two steps that we would need to solve
this question.
Now let's use this to analyze the time complexity involved okay.
So over here notice we are doing a sorting operation.
And let's say there are n items in the array which is given to us.
Again you can you can take this as two n or you can take it as any other variable.
Now to make it very simple, let's just assume that there are n people okay.
So that's the total number of people.
So we are sorting an array which is the cost array which has n elements.
And for doing that we would need to do work of the order of n log n okay.
And then over here we are just iterating through these n elements.
Again please don't get confused that I have written n over here.
Again it's just a variable.
All that I'm saying is if n people is the total number of people.
If that is the case, then the time complexity over here is of the order of n log n and the time complexity,
or the work required to do this operation over here will be of the order of N, because we have to iterate
over the cost array one time.
Okay, now if you want to use two n, you can write two n over here as well, which is of the order
of two n log two n, and this would be of the order of two n.
It does not matter.
You just need to explain what N stands for.
And because these are the components in the solution that take up work, the overall time complexity
of this approach will be of the order of n log n.
Now what about the space complexity when it comes to the space complexity?
If we don't consider the space used by an inbuilt sorting algorithm for the language that you are using,
if we if we assume that we are not considering that space, then the solution that we came up with works
in constant space or the space complexity is of the order of one, because we are not using any auxiliary
space.