1
00:00:00,660 --> 00:00:01,860
Welcome back.

2
00:00:01,860 --> 00:00:09,900
Let's now discuss the space and time complexity of the approach, which we just now discussed for solving

3
00:00:09,900 --> 00:00:11,970
the Elias question over here.

4
00:00:11,970 --> 00:00:16,530
Notice that we are going through all the elements in the array which is given to us.

5
00:00:16,530 --> 00:00:18,300
So that's n operations.

6
00:00:18,300 --> 00:00:26,160
And for each element in the worst case we would have to do log n operations to identify the index where

7
00:00:26,160 --> 00:00:29,160
it has to be inserted in the subsequence that we are building.

8
00:00:29,160 --> 00:00:37,410
So the worst case time complexity or the upper bound is going to be of the order of n into log n n,

9
00:00:37,410 --> 00:00:43,530
because we are iterating through all the elements and log n for doing binary search for each of these

10
00:00:43,530 --> 00:00:48,090
elements, which would need to be done in the worst case scenario.

11
00:00:48,090 --> 00:00:54,930
So the time complexity is going to be of the order of n into log n, and the space complexity of this

12
00:00:54,930 --> 00:01:01,860
solution is going to be of the order of n, because we have to build the subsequence, and this will

13
00:01:01,860 --> 00:01:06,900
take space maximum of the order of n if we can include all the elements, like.

14
00:01:06,900 --> 00:01:12,090
For example, if the array given to us is one, two, three, the subsequence ultimately will be one,

15
00:01:12,090 --> 00:01:12,480
two, three.

16
00:01:12,480 --> 00:01:15,360
So this is going to take space of the order of n.