1
00:00:00,370 --> 00:00:01,480
Welcome back.

2
00:00:01,510 --> 00:00:07,900
Let's now discuss the time and space complexity of the approach that we have just now discussed.

3
00:00:07,900 --> 00:00:15,160
So if you were to consider the results array that we have to return, it would take space of the order

4
00:00:15,160 --> 00:00:22,600
of n factorial into n, because we have seen that for n elements in the input array, there would be

5
00:00:22,600 --> 00:00:28,090
n factorial permutations, and each permutation would have n elements.

6
00:00:28,090 --> 00:00:35,440
So the space required for the array that we would be returning is of the order of n factorial into n.

7
00:00:35,440 --> 00:00:43,390
But then remember, we don't count the space of the answer that we have to return as part of the space

8
00:00:43,390 --> 00:00:49,420
complexity, because this is something that we have to anyway do, no matter what algorithm we use,

9
00:00:49,420 --> 00:00:53,200
because the question itself asks us to return this.

10
00:00:53,200 --> 00:00:57,280
So this is not counted as part of the space complexity.

11
00:00:57,280 --> 00:01:06,700
So the space complexity of this solution is of the order of n, because notice over here that the maximum

12
00:01:06,700 --> 00:01:12,400
depth of the recursive tree at any point in time is of the order of n.

13
00:01:12,400 --> 00:01:17,710
So that is why the space complexity of this solution is of the order of n.

14
00:01:17,710 --> 00:01:20,950
What about the time complexity for this?

15
00:01:20,950 --> 00:01:27,460
Notice that to get one permutation, the perm function is called n times.

16
00:01:27,460 --> 00:01:30,160
If we were to ignore the overlaps.

17
00:01:30,160 --> 00:01:39,100
So for example, to get this permutation, we have called the perm function once, twice and thrice.

18
00:01:39,100 --> 00:01:44,800
So we have called the perm function almost n times to get one permutation.

19
00:01:44,800 --> 00:01:50,980
And again there is no problem in that we are ignoring the overlaps because we are just trying to find

20
00:01:50,980 --> 00:01:55,930
an upper bound of the time complexity which the Big-O notation gives us.

21
00:01:55,930 --> 00:02:01,900
So, ignoring overlaps to get one permutation, we are calling the perm function n times.

22
00:02:01,900 --> 00:02:09,670
And remember we have to ultimately get n factorial permutations, and as we are calling the perm function

23
00:02:09,670 --> 00:02:16,960
n times for one permutation, the total number of times that we are calling the permutation function

24
00:02:16,960 --> 00:02:20,440
is of the order of n into n factorial.

25
00:02:20,440 --> 00:02:22,690
Again, this is an upper bound.

26
00:02:22,690 --> 00:02:29,800
So we have seen that we are calling the perm function n into n factorial times, and out of these.

27
00:02:29,920 --> 00:02:37,000
Out of these n into n factorial times for the cases where we have reached a leaf node.

28
00:02:37,580 --> 00:02:40,100
Which happens n factorial times.

29
00:02:40,250 --> 00:02:46,910
We have to make a copy of the instance of numb's and add it to our results array.

30
00:02:46,940 --> 00:02:52,280
Now making a copy of an array is an O of n time complexity operation.

31
00:02:52,280 --> 00:03:00,680
So for these n factorial cases, the work done is of the order of n factorial into n, and for these

32
00:03:00,680 --> 00:03:07,580
other cases, again, I am just subtracting this from this n factorial, which are the remaining cases

33
00:03:07,580 --> 00:03:13,550
where the perm function is called, and for these instances of the perm function, we are just doing

34
00:03:13,550 --> 00:03:15,530
constant time operations.

35
00:03:15,530 --> 00:03:24,230
So the total time complexity of this solution is this plus this which you can see is of the order of

36
00:03:24,230 --> 00:03:26,120
n into n factorial.

37
00:03:26,120 --> 00:03:31,790
So the time complexity of this solution is of the order of n into n factorial.

38
00:03:31,790 --> 00:03:36,320
And the space complexity of this solution is of the order of n.