Hey there and welcome back!
We have discussed the approach that we can take to recursively visit all the possible strictly increasing
subsequences, and then we would just return the maximum length that we get.
So in this way we can solve the list question in a recursive manner.
We have drawn the recursion tree, and we have also discussed the base case and the choice diagram.
So implementing the code for this solution is going to be very easy.
But over here let's discuss the complexity analysis of the approach that we have come up with.
So what would be the space complexity of this approach.
Notice over here this is a recursive approach.
And we will be taking up space on the recursive call stack.
Now to identify how much space we would take up on the recursive call stack, you just have to take
notice of the maximum depth of the recursion tree.
Notice that the maximum depth of this recursion tree over here is of the order of n.
So that's why the space complexity of this solution is of the order of n.
So over here we have three elements, and the maximum depth of this tree is of the order of n.
Now what about the time complexity?
The time complexity of this solution is of the order of two to the power n, because notice that each
level has two times the nodes that the previous level has, and you have over here approximately a total
of two to the power N nodes.
This is pretty similar to the approach that we have discussed when we discussed the time complexity
of the recursive approach for solving the Fibonacci question.
Now, in each node, notice that we are doing constant amount of work.
So that's why the time complexity is of the order of two to the power n into one, or just two to the
power n.
And just for clarity's sake, what's the constant amount of work that we are doing in each node?
It's to check whether the element at the index score is greater than the element at index prev, or
whether prev is equal to minus one.
Before deciding that we can or cannot include a particular element to the subsequence at hand.
So that's the constant amount of work that we are doing in each node.
So the time complexity of this solution is of the order of two to the power n.
Now you can see that this is not a great time complexity.
And that's why it's time to ask can we do better?
Let's discuss in the next video how we can make this much better by just adding a few lines of code.