1
00:00:00,950 --> 00:00:02,810
Hey there and welcome back!

2
00:00:02,840 --> 00:00:10,430
We have discussed the approach that we can take to recursively visit all the possible strictly increasing

3
00:00:10,430 --> 00:00:15,320
subsequences, and then we would just return the maximum length that we get.

4
00:00:15,320 --> 00:00:20,270
So in this way we can solve the list question in a recursive manner.

5
00:00:20,270 --> 00:00:25,880
We have drawn the recursion tree, and we have also discussed the base case and the choice diagram.

6
00:00:25,880 --> 00:00:29,960
So implementing the code for this solution is going to be very easy.

7
00:00:29,960 --> 00:00:35,330
But over here let's discuss the complexity analysis of the approach that we have come up with.

8
00:00:35,330 --> 00:00:39,500
So what would be the space complexity of this approach.

9
00:00:39,500 --> 00:00:42,500
Notice over here this is a recursive approach.

10
00:00:42,500 --> 00:00:46,850
And we will be taking up space on the recursive call stack.

11
00:00:47,000 --> 00:00:53,600
Now to identify how much space we would take up on the recursive call stack, you just have to take

12
00:00:53,600 --> 00:00:57,500
notice of the maximum depth of the recursion tree.

13
00:00:57,530 --> 00:01:02,960
Notice that the maximum depth of this recursion tree over here is of the order of n.

14
00:01:02,960 --> 00:01:07,670
So that's why the space complexity of this solution is of the order of n.

15
00:01:07,670 --> 00:01:13,520
So over here we have three elements, and the maximum depth of this tree is of the order of n.

16
00:01:13,520 --> 00:01:15,710
Now what about the time complexity?

17
00:01:16,160 --> 00:01:23,480
The time complexity of this solution is of the order of two to the power n, because notice that each

18
00:01:23,480 --> 00:01:33,650
level has two times the nodes that the previous level has, and you have over here approximately a total

19
00:01:33,650 --> 00:01:36,320
of two to the power N nodes.

20
00:01:36,320 --> 00:01:41,780
This is pretty similar to the approach that we have discussed when we discussed the time complexity

21
00:01:41,780 --> 00:01:45,710
of the recursive approach for solving the Fibonacci question.

22
00:01:45,710 --> 00:01:51,680
Now, in each node, notice that we are doing constant amount of work.

23
00:01:51,680 --> 00:01:58,130
So that's why the time complexity is of the order of two to the power n into one, or just two to the

24
00:01:58,130 --> 00:01:59,030
power n.

25
00:01:59,030 --> 00:02:05,300
And just for clarity's sake, what's the constant amount of work that we are doing in each node?

26
00:02:05,300 --> 00:02:11,840
It's to check whether the element at the index score is greater than the element at index prev, or

27
00:02:11,840 --> 00:02:13,640
whether prev is equal to minus one.

28
00:02:13,640 --> 00:02:19,130
Before deciding that we can or cannot include a particular element to the subsequence at hand.

29
00:02:19,130 --> 00:02:23,240
So that's the constant amount of work that we are doing in each node.

30
00:02:23,630 --> 00:02:28,160
So the time complexity of this solution is of the order of two to the power n.

31
00:02:28,160 --> 00:02:31,250
Now you can see that this is not a great time complexity.

32
00:02:31,250 --> 00:02:35,390
And that's why it's time to ask can we do better?

33
00:02:35,420 --> 00:02:43,250
Let's discuss in the next video how we can make this much better by just adding a few lines of code.