1
00:00:00,620 --> 00:00:05,480
In the previous video, we came up with this pseudo code for solving this question.

2
00:00:05,510 --> 00:00:12,770
Now let's think of the space and time complexity for this approach for solving the task scheduler problem.

3
00:00:12,770 --> 00:00:14,390
Okay, now for this.

4
00:00:14,390 --> 00:00:19,460
Let's take a look at what are the aspects in this solution that take up work.

5
00:00:19,460 --> 00:00:19,940
Okay.

6
00:00:19,940 --> 00:00:27,530
We can see that this aspect over here, which is traversing the tasks and calculating task frequencies,

7
00:00:27,530 --> 00:00:33,200
takes up work of the order of n where n is the size of the tasks array.

8
00:00:33,200 --> 00:00:40,160
And again it's o of n because we have to traverse or pass through once the elements in the tasks array.

9
00:00:40,160 --> 00:00:40,670
Okay.

10
00:00:40,670 --> 00:00:48,770
And then these aspects over here are just O of one time complexity operations or constant time operations

11
00:00:48,770 --> 00:00:50,780
because we're just doing a few calculations.

12
00:00:50,780 --> 00:00:51,110
Right.

13
00:00:51,110 --> 00:00:57,500
So that's why the total time complexity of this solution is of the order of n.

14
00:00:57,650 --> 00:01:00,020
Now what about the space complexity?

15
00:01:00,020 --> 00:01:05,930
The space complexity of this approach is of the order of one or constant space.

16
00:01:05,930 --> 00:01:07,520
Now why is this the case?

17
00:01:07,520 --> 00:01:15,230
You may say that we are using space because we have an array which is used to store the frequency of

18
00:01:15,230 --> 00:01:16,940
the tasks which are given to us.

19
00:01:16,940 --> 00:01:22,340
But then in the question, it's mentioned that the tasks go from A to Z.

20
00:01:22,370 --> 00:01:26,420
Okay, so that's a maximum of 26 different tasks.

21
00:01:26,420 --> 00:01:34,610
And therefore the space of this array which is used to store the frequencies is not varying based on

22
00:01:34,610 --> 00:01:35,630
the input size.

23
00:01:35,630 --> 00:01:35,960
Okay.

24
00:01:35,960 --> 00:01:40,040
So that's why the space complexity is just constant.

25
00:01:40,040 --> 00:01:48,440
Remember O of 26 space complexity is one and the same as O of one, because we are not using up varying

26
00:01:48,440 --> 00:01:50,690
space based on the input size.

27
00:01:50,690 --> 00:01:55,160
So the space complexity of this solution is of the order of one.