1
00:00:00,730 --> 00:00:01,900
Welcome back.

2
00:00:01,900 --> 00:00:07,660
Let's take a look at the space and time complexity of the approach that we have discussed.

3
00:00:07,660 --> 00:00:15,100
So the time complexity of this approach is going to be of the order of n into two to the power n.

4
00:00:15,100 --> 00:00:16,030
Now why is that.

5
00:00:16,030 --> 00:00:21,010
So first of all, notice that there are two to the power n subsets.

6
00:00:21,010 --> 00:00:22,660
We have already discussed this.

7
00:00:22,660 --> 00:00:30,010
And this is because for each element we have two choices which is either include that element or not

8
00:00:30,010 --> 00:00:31,060
include that element.

9
00:00:31,060 --> 00:00:35,200
So let's say we are given three elements over here in the array.

10
00:00:35,200 --> 00:00:41,740
So we have two choices for the first element, two choices for the second element, and again two choices

11
00:00:41,740 --> 00:00:42,970
for the third element.

12
00:00:42,970 --> 00:00:49,510
So the total number of subsets or choices that we have is two into two into two, which is equal to

13
00:00:49,510 --> 00:00:49,870
eight.

14
00:00:49,870 --> 00:00:56,410
So that is how you can see we have 123456788 subsets over here.

15
00:00:56,410 --> 00:00:59,200
So there are two to the power n subsets.

16
00:00:59,200 --> 00:01:07,930
And for getting to each subset notice that we are calling the subsets function or the helper function

17
00:01:07,930 --> 00:01:10,300
recursively n times.

18
00:01:10,720 --> 00:01:11,260
All right.

19
00:01:11,260 --> 00:01:13,210
So for getting one subset.

20
00:01:14,320 --> 00:01:16,300
The function is called.

21
00:01:17,450 --> 00:01:18,620
N times.

22
00:01:21,650 --> 00:01:24,860
And remember this is if we ignore overlaps.

23
00:01:28,100 --> 00:01:34,460
Now, ignoring overlaps means, for example, the same function is called to get to this subset as well

24
00:01:34,460 --> 00:01:37,370
as this subset, but we are ignoring this overlap.

25
00:01:37,370 --> 00:01:44,930
Now, it's okay to ignore overlaps because we are just trying to get a upper bound for the work to be

26
00:01:44,930 --> 00:01:47,330
done, which is what Big-O gives, right?

27
00:01:47,330 --> 00:01:49,400
So we are just getting an upper bound.

28
00:01:49,400 --> 00:01:51,920
Therefore ignoring overlaps is okay.

29
00:01:51,920 --> 00:01:59,060
So again, the time complexity is of the order of n into two to the power n, because for getting one

30
00:01:59,060 --> 00:02:01,640
subset, we are calling the function n times.

31
00:02:01,640 --> 00:02:06,170
And in each of these calls we are doing some constant time operations.

32
00:02:06,170 --> 00:02:14,900
So to get two to the power n subsets will have to do n into two to the power n calls to the function

33
00:02:14,900 --> 00:02:19,370
that we are recursively calling, and therefore this is the total number of calls that the function

34
00:02:19,370 --> 00:02:20,030
is called.

35
00:02:20,030 --> 00:02:24,440
And in each of these calls we are doing constant time operations.

36
00:02:24,440 --> 00:02:31,820
So the time complexity is of the order of n into two to the power n into one, or of the order of n

37
00:02:31,820 --> 00:02:33,890
into two to the power n.

38
00:02:33,890 --> 00:02:42,380
Now, when it comes to the space complexity, it's of the order of n because of the depth of the recursion

39
00:02:42,380 --> 00:02:43,100
tree over here.

40
00:02:43,100 --> 00:02:50,660
Notice the maximum depth is of the order of n, so the space complexity is of the order of n because

41
00:02:50,660 --> 00:02:54,230
we are using space on the recursive call stack.

42
00:02:54,890 --> 00:03:03,950
Now remember in coding interviews, if we need to take up space just to return the output which is asked

43
00:03:03,950 --> 00:03:11,840
of us, that space is not calculated as part of the space complexity, because it is space that we will

44
00:03:11,840 --> 00:03:19,460
have to use no matter what algorithm or approach we take, because the question itself asks us to return

45
00:03:19,460 --> 00:03:19,760
that.

46
00:03:19,760 --> 00:03:26,780
So the space of the array which is returned, which has all the subsets, is not calculated as part

47
00:03:26,780 --> 00:03:27,980
of the space complexity.

48
00:03:27,980 --> 00:03:31,610
So that is why the space complexity is of the order of n.

49
00:03:31,610 --> 00:03:37,070
And as we discussed, the time complexity is of the order of n into two to the power n.