1
00:00:00,140 --> 00:00:01,910
Hey there and welcome back.

2
00:00:01,910 --> 00:00:08,030
So we have discussed the greedy algorithm that we can use to solve the two city scheduling question.

3
00:00:08,030 --> 00:00:13,910
Now let's go ahead and discuss the space and time complexity of the approach that we came up with.

4
00:00:13,910 --> 00:00:19,490
Now in the previous video, we have discussed that these are the two steps that we would need to solve

5
00:00:19,490 --> 00:00:20,180
this question.

6
00:00:20,180 --> 00:00:24,740
Now let's use this to analyze the time complexity involved okay.

7
00:00:24,740 --> 00:00:28,100
So over here notice we are doing a sorting operation.

8
00:00:28,100 --> 00:00:33,860
And let's say there are n items in the array which is given to us.

9
00:00:33,890 --> 00:00:38,720
Again you can you can take this as two n or you can take it as any other variable.

10
00:00:38,720 --> 00:00:43,190
Now to make it very simple, let's just assume that there are n people okay.

11
00:00:43,190 --> 00:00:45,170
So that's the total number of people.

12
00:00:45,170 --> 00:00:50,060
So we are sorting an array which is the cost array which has n elements.

13
00:00:50,060 --> 00:00:56,030
And for doing that we would need to do work of the order of n log n okay.

14
00:00:56,030 --> 00:01:00,470
And then over here we are just iterating through these n elements.

15
00:01:00,470 --> 00:01:03,980
Again please don't get confused that I have written n over here.

16
00:01:03,980 --> 00:01:05,840
Again it's just a variable.

17
00:01:05,840 --> 00:01:10,070
All that I'm saying is if n people is the total number of people.

18
00:01:10,880 --> 00:01:17,570
If that is the case, then the time complexity over here is of the order of n log n and the time complexity,

19
00:01:17,570 --> 00:01:23,540
or the work required to do this operation over here will be of the order of N, because we have to iterate

20
00:01:23,540 --> 00:01:25,520
over the cost array one time.

21
00:01:25,520 --> 00:01:30,440
Okay, now if you want to use two n, you can write two n over here as well, which is of the order

22
00:01:30,440 --> 00:01:33,650
of two n log two n, and this would be of the order of two n.

23
00:01:33,650 --> 00:01:34,700
It does not matter.

24
00:01:34,700 --> 00:01:37,220
You just need to explain what N stands for.

25
00:01:37,220 --> 00:01:43,460
And because these are the components in the solution that take up work, the overall time complexity

26
00:01:43,460 --> 00:01:47,060
of this approach will be of the order of n log n.

27
00:01:47,060 --> 00:01:51,980
Now what about the space complexity when it comes to the space complexity?

28
00:01:51,980 --> 00:01:59,570
If we don't consider the space used by an inbuilt sorting algorithm for the language that you are using,

29
00:01:59,570 --> 00:02:06,470
if we if we assume that we are not considering that space, then the solution that we came up with works

30
00:02:06,470 --> 00:02:13,880
in constant space or the space complexity is of the order of one, because we are not using any auxiliary

31
00:02:13,880 --> 00:02:14,540
space.