1
00:00:00,500 --> 00:00:01,700
Welcome back.

2
00:00:01,700 --> 00:00:08,960
In this video, let's discuss the time and space complexity of the approach that we have taken to come

3
00:00:08,960 --> 00:00:13,970
up with all the possible combinations where n and k are given to us.

4
00:00:14,000 --> 00:00:21,380
Now, when it comes to the time complexity of a recursive solution, we have discussed that we can identify

5
00:00:21,380 --> 00:00:28,670
it by multiplying the number of nodes in the recursive tree, with the work done at each individual

6
00:00:28,670 --> 00:00:32,960
node to identify the number of nodes.

7
00:00:32,990 --> 00:00:42,680
Let's make an observation notice over here that to get to each combination, we have to call the function

8
00:00:42,680 --> 00:00:51,650
that we are recursively calling k times, or we need k nodes to identify each possible combination.

9
00:00:51,680 --> 00:00:56,750
Notice over here this was one comma two comma three is a possible combination.

10
00:00:56,750 --> 00:01:03,800
And to get to this we had to make three recursive calls to the function which we are using.

11
00:01:03,800 --> 00:01:10,460
So to get to each combination we have to make k calls to the recursive function.

12
00:01:10,460 --> 00:01:12,830
Or we need k nodes.

13
00:01:12,830 --> 00:01:20,300
And when it comes to the number of combinations that are possible where n and k are given, we can find

14
00:01:20,300 --> 00:01:23,630
it using n, c, k and c.

15
00:01:23,630 --> 00:01:30,530
K is just a notation to indicate how many combinations can be made of length k.

16
00:01:30,800 --> 00:01:33,830
When we use the numbers from one to n.

17
00:01:33,830 --> 00:01:41,990
Now, using these two pieces of information, we can identify the number of nodes that are there in

18
00:01:41,990 --> 00:01:43,190
the recursive tree.

19
00:01:43,190 --> 00:01:46,850
And again we are just trying to find an upper bound.

20
00:01:46,850 --> 00:01:49,640
And we are going to ignore overlaps.

21
00:01:49,640 --> 00:01:55,550
So if we want to find an upper bound ignoring overlaps we can just multiply these two.

22
00:01:55,580 --> 00:01:59,570
So the number of nodes will be k into n c k.

23
00:01:59,630 --> 00:02:03,170
Now a quick side note on what n c k is.

24
00:02:03,800 --> 00:02:05,390
Again this is a side note.

25
00:02:05,870 --> 00:02:09,800
If we have n equal to four that's 1234.

26
00:02:09,800 --> 00:02:12,080
And let's say k is equal to two.

27
00:02:12,110 --> 00:02:15,740
We have seen that we can arrive at six combinations.

28
00:02:15,770 --> 00:02:21,800
Now this six over here can also be calculated as 4C2.

29
00:02:21,800 --> 00:02:24,950
Notice over here n is four because that's what's given.

30
00:02:24,950 --> 00:02:26,720
And k is equal to two.

31
00:02:26,750 --> 00:02:28,160
So we have two over here.

32
00:02:28,160 --> 00:02:32,510
So we are writing n c k as 4C2 over here.

33
00:02:32,510 --> 00:02:40,250
And the generic formula for n c k is n factorial by k factorial into n minus k factorial.

34
00:02:40,250 --> 00:02:46,700
I'm sure this is something that you must have encountered in your mathematics classes, but over here

35
00:02:46,700 --> 00:02:52,790
we are just having a quick side note again n factorial is one into two into three, etc. up to n.

36
00:02:52,790 --> 00:02:55,310
So let's substitute this over here.

37
00:02:55,310 --> 00:02:57,320
So we need n factorial.

38
00:02:57,320 --> 00:02:59,210
And in this case n is four.

39
00:02:59,210 --> 00:03:01,640
So we have four factorial in the numerator.

40
00:03:01,640 --> 00:03:04,010
And then over here we need k factorial.

41
00:03:04,010 --> 00:03:05,930
So that's this two factorial.

42
00:03:05,930 --> 00:03:11,120
And then we need n minus k factorial which is this four minus two factorial.

43
00:03:11,120 --> 00:03:17,840
So this simplifies to four factorial divided by two factorial into two factorial.

44
00:03:17,840 --> 00:03:24,650
Now four factorial is four into three into two into one, which is 24, and two factorial is one into

45
00:03:24,650 --> 00:03:25,940
two, which is two.

46
00:03:25,940 --> 00:03:28,880
And again we have two factorial over here, which is two.

47
00:03:28,880 --> 00:03:31,940
So 24 divided by four gives us six.

48
00:03:31,940 --> 00:03:35,240
So that is why 4C2 is equal to six.

49
00:03:35,240 --> 00:03:42,230
And in general terms to identify the possible number of combinations, all we need to do is we need

50
00:03:42,230 --> 00:03:44,150
to identify n c k.

51
00:03:44,510 --> 00:03:45,200
All right.

52
00:03:45,230 --> 00:03:52,400
Now coming back to the approach that we discussed to identify the upper bound of the number of nodes,

53
00:03:52,400 --> 00:03:56,030
we just need to multiply k and n c k.

54
00:03:56,480 --> 00:04:04,040
Because for each combination we are making k calls to the recursive function that we will be writing.

55
00:04:04,040 --> 00:04:08,300
And in total we'll be having n c k combinations.

56
00:04:08,300 --> 00:04:15,770
Therefore, the number of nodes or the upper bound of the number of nodes will be k into n, c, k,

57
00:04:15,770 --> 00:04:23,660
and in each call we are just doing constant time operations, which is like adding the value or appending

58
00:04:23,660 --> 00:04:26,330
the value of j and then popping that value.

59
00:04:26,330 --> 00:04:33,590
So in each call we are just doing constant time operations or O of one time complexity operations.

60
00:04:33,590 --> 00:04:42,230
So this is why the time complexity of this solution is of the order of k into n c k and n c k, as we

61
00:04:42,230 --> 00:04:47,720
have discussed, is n factorial divided by k factorial into n minus k factorial.

62
00:04:47,720 --> 00:04:56,300
So the time complexity is of the order of k into n factorial by k factorial into n minus k factorial.

63
00:04:57,970 --> 00:05:03,220
The space complexity of this solution is of the order of k, because.

64
00:05:03,220 --> 00:05:10,690
Notice over here, the maximum depth of the recursive tree at any point is k, so the space complexity

65
00:05:10,690 --> 00:05:16,060
is of the order of k because we are using space on the recursive call stack.

66
00:05:16,090 --> 00:05:24,760
Do remember that we don't calculate the space required to return the answer as part of the space complexity,

67
00:05:24,760 --> 00:05:31,300
because that's something the question asks us to do, and we would have to do that no matter what approach

68
00:05:31,300 --> 00:05:32,170
we take.