1
00:00:00,110 --> 00:00:01,910
Hey there and welcome back.

2
00:00:01,910 --> 00:00:09,800
In this video, let's discuss how to think about the complexity analysis for recursive solutions.

3
00:00:10,130 --> 00:00:15,440
Let's say that for a question at hand you are able to draw a recursive tree.

4
00:00:15,440 --> 00:00:17,690
And let's say it looks like this.

5
00:00:19,090 --> 00:00:26,950
Now to find the time complexity, all you need to do is you need to identify the number of nodes that

6
00:00:26,950 --> 00:00:29,230
are there in the recursive tree.

7
00:00:29,230 --> 00:00:35,020
And then you need to multiply this with the work done in each node.

8
00:00:40,780 --> 00:00:48,160
You will see more of this in action in different videos where we discuss the time complexity of recursive

9
00:00:48,160 --> 00:00:48,880
solutions.

10
00:00:48,880 --> 00:00:50,770
So this is the general case.

11
00:00:50,770 --> 00:00:58,060
Now you will have some questions where for example, leaf nodes will do some actions, but then the

12
00:00:58,060 --> 00:01:00,670
other nodes will do some other actions.

13
00:01:00,670 --> 00:01:07,540
Now in that case you just need to identify the number of leaf nodes and multiply that with the work

14
00:01:07,540 --> 00:01:14,650
done in a leaf node, and then add to it the number of other nodes and multiply it to this the work

15
00:01:14,650 --> 00:01:16,120
done in other nodes.

16
00:01:16,120 --> 00:01:20,950
So this will give you the time complexity in such scenarios.

17
00:01:21,130 --> 00:01:28,270
Now when it comes to the space complexity, and if you are only considering the recursion of the solution,

18
00:01:28,270 --> 00:01:34,900
then you just need to know the maximum depth of the recursion tree, because that will tell you the

19
00:01:34,900 --> 00:01:38,320
space you stub on the recursive call stack.

20
00:01:38,320 --> 00:01:39,400
For example.

21
00:01:39,400 --> 00:01:43,570
In this case, notice that the maximum depth is equal to three.

22
00:01:43,570 --> 00:01:49,180
And let's say in this particular question this is three because three is the input size.

23
00:01:49,180 --> 00:01:56,230
And if we call that n, the space used on the recursive call stack would be of the order of n.

24
00:01:56,230 --> 00:02:02,440
And the recursion tree will help you understand this, because these would be the maximum number of

25
00:02:02,440 --> 00:02:08,050
calls which would be there on the recursive call stack at any point of time.

26
00:02:08,050 --> 00:02:17,800
So notice how drawing the recursion tree is extremely useful to find the time and space complexity of

27
00:02:17,800 --> 00:02:19,270
recursive solutions.