Hey there and welcome back.
In this video, let's discuss how to think about the complexity analysis for recursive solutions.
Let's say that for a question at hand you are able to draw a recursive tree.
And let's say it looks like this.
Now to find the time complexity, all you need to do is you need to identify the number of nodes that
are there in the recursive tree.
And then you need to multiply this with the work done in each node.
You will see more of this in action in different videos where we discuss the time complexity of recursive
solutions.
So this is the general case.
Now you will have some questions where for example, leaf nodes will do some actions, but then the
other nodes will do some other actions.
Now in that case you just need to identify the number of leaf nodes and multiply that with the work
done in a leaf node, and then add to it the number of other nodes and multiply it to this the work
done in other nodes.
So this will give you the time complexity in such scenarios.
Now when it comes to the space complexity, and if you are only considering the recursion of the solution,
then you just need to know the maximum depth of the recursion tree, because that will tell you the
space you stub on the recursive call stack.
For example.
In this case, notice that the maximum depth is equal to three.
And let's say in this particular question this is three because three is the input size.
And if we call that n, the space used on the recursive call stack would be of the order of n.
And the recursion tree will help you understand this, because these would be the maximum number of
calls which would be there on the recursive call stack at any point of time.
So notice how drawing the recursion tree is extremely useful to find the time and space complexity of
recursive solutions.