1
00:00:00,140 --> 00:00:07,910
In a previous video, we have seen that the maximum depth of this recursive tree is going to be T divided

2
00:00:07,910 --> 00:00:15,590
by m, where t is the target and m is the minimum value among the candidates given in the candidates

3
00:00:15,590 --> 00:00:16,040
array.

4
00:00:16,490 --> 00:00:24,170
Let's now see how we can make use of this to find the upper bound of the number of nodes in this recursive

5
00:00:24,200 --> 00:00:24,710
tree.

6
00:00:25,070 --> 00:00:32,180
In the previous video, we saw that if a tree is such that every node has three nodes.

7
00:00:33,060 --> 00:00:34,740
And it goes on in this manner.

8
00:00:34,740 --> 00:00:41,640
Then the maximum number of nodes that can be there in this tree would be equal to three to the power.

9
00:00:41,640 --> 00:00:44,460
The height of this tree over here.

10
00:00:44,460 --> 00:00:47,400
The maximum height of this tree plus one.

11
00:00:48,090 --> 00:00:56,100
So in this same manner over here, the maximum number of nodes that can be there for every node is equal

12
00:00:56,100 --> 00:01:05,310
to n, and therefore the maximum number of nodes in this recursive tree is equal to n to the power t

13
00:01:05,310 --> 00:01:06,750
by m plus one.

14
00:01:06,750 --> 00:01:11,040
Because t by m is the maximum height of this recursive tree.

15
00:01:11,070 --> 00:01:15,660
So we have found the maximum number of nodes in this recursive tree.

16
00:01:15,660 --> 00:01:23,910
And because in each node we are doing constant time operations, the time complexity of this approach

17
00:01:23,910 --> 00:01:31,620
is of the order of n to the power t by m plus one into one, or just n to the power t by m plus one.

18
00:01:31,620 --> 00:01:34,440
So this is the time complexity of this approach.

19
00:01:35,010 --> 00:01:41,880
Now when it comes to the space complexity, it's going to be of the order of t divided by m, because

20
00:01:41,880 --> 00:01:47,580
t by m is the maximum height or maximum depth of the recursive tree over here.

21
00:01:47,580 --> 00:01:52,230
And and we will be using this space on the recursive call stack.

22
00:01:52,230 --> 00:01:55,740
So the space complexity is of the order of t by m.

23
00:01:55,740 --> 00:02:02,550
Also notice that the current array which is used to build each of these combinations, will also take

24
00:02:02,550 --> 00:02:10,410
up space of the order of t by m, because t by m is the maximum size of the current array at any point.

25
00:02:10,410 --> 00:02:15,960
So for example, over here, notice that this is the maximum size which is four elements.

26
00:02:15,960 --> 00:02:22,620
The reason for this is the same reason as to why the maximum depth of this recursive tree over here

27
00:02:22,620 --> 00:02:25,440
is t by m, because m is the minimum value.

28
00:02:25,440 --> 00:02:33,180
And if we add m t by m times, we will either get a combination of coeur which is greater than the target

29
00:02:33,180 --> 00:02:35,400
value or equal to the target value.

30
00:02:35,400 --> 00:02:39,540
And this is going to be the largest instance for the current array.

31
00:02:39,540 --> 00:02:46,200
So the time complexity is of the order of n to the power t by m plus one, and the space complexity

32
00:02:46,200 --> 00:02:48,060
is of the order of T by m.

33
00:02:48,060 --> 00:02:55,890
Now also do remember when we calculate the space complexity, we do not consider the space needed just

34
00:02:55,890 --> 00:02:59,460
to hold the answer and return it as part of the space complexity.

35
00:02:59,460 --> 00:03:03,330
So in this case, the results array also takes up space.

36
00:03:03,330 --> 00:03:06,510
But we don't consider that as part of the space complexity.

37
00:03:06,510 --> 00:03:10,500
And that's why the space complexity of this solution is of the order of T by.