1
00:00:00,490 --> 00:00:01,600
Welcome back.

2
00:00:01,600 --> 00:00:07,780
Let's now discuss the space and time complexity for the approach that we have discussed in the previous

3
00:00:07,780 --> 00:00:08,500
video.

4
00:00:08,530 --> 00:00:16,630
The time complexity for this approach is going to be of the order of n squared, where n is the number

5
00:00:16,630 --> 00:00:19,090
of elements in the array which is given to us.

6
00:00:19,120 --> 00:00:20,830
Now why is that the case?

7
00:00:20,860 --> 00:00:27,490
Let's think of what are the different aspects which contribute to the time complexity of this approach.

8
00:00:27,490 --> 00:00:32,500
As we have discussed, we first need to sort the array which is given to us.

9
00:00:32,500 --> 00:00:40,060
And if this array over here has n elements, sorting this array will take work of the order of n log

10
00:00:40,060 --> 00:00:40,510
n.

11
00:00:40,960 --> 00:00:48,220
The other aspect that takes up work over here is the nested for loop, which we will need to move the

12
00:00:48,220 --> 00:00:50,470
I and j pointers.

13
00:00:50,680 --> 00:00:58,540
Now, in the nested for loop, we know that I goes from one up to n minus one, and j goes from zero

14
00:00:58,540 --> 00:01:02,140
to I minus one for each instance of I.

15
00:01:02,230 --> 00:01:08,680
Now an upper bound for this nested for loop will be of the order of n square.

16
00:01:08,680 --> 00:01:09,100
Okay.

17
00:01:09,100 --> 00:01:13,450
So again this can be said as approximately n operations.

18
00:01:13,450 --> 00:01:17,500
And over here also the upper bound for this would be n operations.

19
00:01:17,500 --> 00:01:22,870
So that's why the upper bound for the nested for loop is of the order of n square.

20
00:01:22,870 --> 00:01:27,400
And between n square and n log n n square is greater.

21
00:01:27,400 --> 00:01:32,710
And that's why the time complexity of this approach is of the order of n squared.

22
00:01:32,740 --> 00:01:35,170
Now what about the space complexity?

23
00:01:35,170 --> 00:01:40,960
The space complexity of this solution is going to be of the order of n.

24
00:01:40,960 --> 00:01:42,640
Now why is that the case?

25
00:01:42,640 --> 00:01:48,730
Or let's think of what are the aspects that take up auxiliary space in this solution.

26
00:01:48,940 --> 00:01:56,920
Now in this solution, the only thing that takes up extra space is the 1d dp array, which we have used

27
00:01:56,920 --> 00:01:57,520
over here.

28
00:01:57,520 --> 00:02:03,070
And as you can see over here, it has n elements or it can store n elements.

29
00:02:03,070 --> 00:02:08,710
And that's why we are taking up space of the order of n for creating this DP array.

30
00:02:08,710 --> 00:02:15,460
So the time complexity is of the order of n square, and the space complexity is of the order of n.