1
00:00:00,140 --> 00:00:06,800
Let's now discuss the time and space complexity of the approach that we just now discussed.

2
00:00:06,800 --> 00:00:13,940
So the time and space complexity of this solution is going to be similar to the time and space complexity

3
00:00:13,940 --> 00:00:21,680
of the Subset's question, because in the worst case, it's possible that there is no repetition in

4
00:00:21,680 --> 00:00:23,840
the input array which is given to us.

5
00:00:23,840 --> 00:00:27,620
So over here notice that n is equal to four.

6
00:00:27,650 --> 00:00:33,950
There are four elements in the input array and two to the power n in this case is equal to 16.

7
00:00:33,950 --> 00:00:36,950
But we are only having 12 subsets.

8
00:00:37,370 --> 00:00:40,970
We only have 12 subsets because we have removed duplicates.

9
00:00:40,970 --> 00:00:47,630
But again in the worst case, if there are no duplicates, we would still have two to the power n subsets,

10
00:00:47,630 --> 00:00:54,020
and we are doing n calls to the recursive function to get those two to the power n subsets.

11
00:00:54,020 --> 00:00:57,500
And in each call we are doing constant time operations.

12
00:00:57,500 --> 00:01:02,510
So the time complexity of this solution is O of n into two to the power n.

13
00:01:02,510 --> 00:01:10,730
And the space complexity of this solution is O of n, because space is used up on the recursion call

14
00:01:10,730 --> 00:01:11,120
stack.

15
00:01:11,120 --> 00:01:18,920
Now again remember in this solution initially we are sorting the array which is an o of n log n time

16
00:01:18,920 --> 00:01:20,210
complexity operation.

17
00:01:20,210 --> 00:01:27,740
But then n into two to the power n is much higher than n log n, and therefore we can ignore this.

18
00:01:27,740 --> 00:01:35,120
So the time complexity is o of n into two to the power n, and the space complexity is O of n.

19
00:01:35,120 --> 00:01:40,670
If we ignore any space that's taken up while sorting the array.