1
00:00:00,230 --> 00:00:05,180
In the previous video, we have discussed the approach for solving the combinations.

2
00:00:05,180 --> 00:00:06,740
Sum one question.

3
00:00:06,740 --> 00:00:12,470
Now let's try to think about the space and time complexity of this approach.

4
00:00:12,830 --> 00:00:21,620
If n is the number of candidates in the candidates array which is given to us, and if T is the target

5
00:00:21,620 --> 00:00:30,290
value, and if M is the minimum value among the candidates or the integers in the candidates array.

6
00:00:30,290 --> 00:00:33,110
For example, over here, two is the minimum value.

7
00:00:33,110 --> 00:00:42,320
So if M is the minimum value among the candidates, then notice that for the recursion tree, the maximum

8
00:00:42,320 --> 00:00:46,190
depth would be equal to t divided by m.

9
00:00:46,670 --> 00:00:48,260
Now why is that the case.

10
00:00:48,260 --> 00:00:52,520
Because notice over here for example two was the minimum value.

11
00:00:52,520 --> 00:00:54,440
So initially we added two.

12
00:00:54,470 --> 00:00:56,630
Then we again added two over here.

13
00:00:56,630 --> 00:00:58,940
And again we add two over here.

14
00:00:58,940 --> 00:01:03,260
And in the next level we would again add one more time two.

15
00:01:03,260 --> 00:01:08,210
And at this point two plus two plus two plus two is equal to eight.

16
00:01:08,210 --> 00:01:11,360
And eight is greater than the target value which is seven.

17
00:01:11,360 --> 00:01:13,790
So this branch over here would be pruned.

18
00:01:13,790 --> 00:01:18,560
But this would be the branch which has the greatest depth.

19
00:01:18,560 --> 00:01:23,780
So that's why the maximum depth of the tree would be equal to t divided by m.

20
00:01:23,780 --> 00:01:31,760
Because in this case we are adding the lowest value till either we get the sum to be equal to the target

21
00:01:31,760 --> 00:01:35,300
value, or the sum to be greater than the target value.

22
00:01:35,300 --> 00:01:41,180
Now again for example, target could have been eight, and in that case two plus two plus two plus two

23
00:01:41,210 --> 00:01:42,440
would be equal to eight.

24
00:01:42,440 --> 00:01:46,130
And we would stop going down further or in.

25
00:01:46,130 --> 00:01:50,570
As you can see over here this sum is eight which is greater than seven.

26
00:01:50,570 --> 00:01:56,480
So this would give us or t by m will give us the maximum depth of the tree.

27
00:01:56,480 --> 00:02:04,190
And that is the case because we are adding the least value t by m times till the sum of the elements

28
00:02:04,190 --> 00:02:09,800
in the current array is equal to the target value, or greater than the target value.

29
00:02:10,280 --> 00:02:16,100
Coming back to what we are trying to do over here, we are trying to find the space and time complexity

30
00:02:16,100 --> 00:02:18,500
of the approach that we have previously discussed.

31
00:02:18,500 --> 00:02:24,320
And for this, we are trying to find the number of nodes, or the upper bound of the number of nodes

32
00:02:24,320 --> 00:02:26,090
in the recursion tree over here.

33
00:02:26,090 --> 00:02:30,800
Because if we know that we can make use of that to find the time and space complexity.

34
00:02:30,800 --> 00:02:38,030
So we have seen that the maximum depth of the tree or the recursive tree is t divided by m.

35
00:02:38,030 --> 00:02:45,230
Now let's see how we can use this to find the upper bound of the number of nodes in this tree.