Welcome back.
Let's now discuss the time and space complexity of the approach that we have just now discussed.
So if you were to consider the results array that we have to return, it would take space of the order
of n factorial into n, because we have seen that for n elements in the input array, there would be
n factorial permutations, and each permutation would have n elements.
So the space required for the array that we would be returning is of the order of n factorial into n.
But then remember, we don't count the space of the answer that we have to return as part of the space
complexity, because this is something that we have to anyway do, no matter what algorithm we use,
because the question itself asks us to return this.
So this is not counted as part of the space complexity.
So the space complexity of this solution is of the order of n, because notice over here that the maximum
depth of the recursive tree at any point in time is of the order of n.
So that is why the space complexity of this solution is of the order of n.
What about the time complexity for this?
Notice that to get one permutation, the perm function is called n times.
If we were to ignore the overlaps.
So for example, to get this permutation, we have called the perm function once, twice and thrice.
So we have called the perm function almost n times to get one permutation.
And again there is no problem in that we are ignoring the overlaps because we are just trying to find
an upper bound of the time complexity which the Big-O notation gives us.
So, ignoring overlaps to get one permutation, we are calling the perm function n times.
And remember we have to ultimately get n factorial permutations, and as we are calling the perm function
n times for one permutation, the total number of times that we are calling the permutation function
is of the order of n into n factorial.
Again, this is an upper bound.
So we have seen that we are calling the perm function n into n factorial times, and out of these.
Out of these n into n factorial times for the cases where we have reached a leaf node.
Which happens n factorial times.
We have to make a copy of the instance of numb's and add it to our results array.
Now making a copy of an array is an O of n time complexity operation.
So for these n factorial cases, the work done is of the order of n factorial into n, and for these
other cases, again, I am just subtracting this from this n factorial, which are the remaining cases
where the perm function is called, and for these instances of the perm function, we are just doing
constant time operations.
So the total time complexity of this solution is this plus this which you can see is of the order of
n into n factorial.
So the time complexity of this solution is of the order of n into n factorial.
And the space complexity of this solution is of the order of n.