Welcome back.
Let's take a look at the space and time complexity of the approach that we have discussed.
So the time complexity of this approach is going to be of the order of n into two to the power n.
Now why is that.
So first of all, notice that there are two to the power n subsets.
We have already discussed this.
And this is because for each element we have two choices which is either include that element or not
include that element.
So let's say we are given three elements over here in the array.
So we have two choices for the first element, two choices for the second element, and again two choices
for the third element.
So the total number of subsets or choices that we have is two into two into two, which is equal to
eight.
So that is how you can see we have 123456788 subsets over here.
So there are two to the power n subsets.
And for getting to each subset notice that we are calling the subsets function or the helper function
recursively n times.
All right.
So for getting one subset.
The function is called.
N times.
And remember this is if we ignore overlaps.
Now, ignoring overlaps means, for example, the same function is called to get to this subset as well
as this subset, but we are ignoring this overlap.
Now, it's okay to ignore overlaps because we are just trying to get a upper bound for the work to be
done, which is what Big-O gives, right?
So we are just getting an upper bound.
Therefore ignoring overlaps is okay.
So again, the time complexity is of the order of n into two to the power n, because for getting one
subset, we are calling the function n times.
And in each of these calls we are doing some constant time operations.
So to get two to the power n subsets will have to do n into two to the power n calls to the function
that we are recursively calling, and therefore this is the total number of calls that the function
is called.
And in each of these calls we are doing constant time operations.
So the time complexity is of the order of n into two to the power n into one, or of the order of n
into two to the power n.
Now, when it comes to the space complexity, it's of the order of n because of the depth of the recursion
tree over here.
Notice the maximum depth is of the order of n, so the space complexity is of the order of n because
we are using space on the recursive call stack.
Now remember in coding interviews, if we need to take up space just to return the output which is asked
of us, that space is not calculated as part of the space complexity, because it is space that we will
have to use no matter what algorithm or approach we take, because the question itself asks us to return
that.
So the space of the array which is returned, which has all the subsets, is not calculated as part
of the space complexity.
So that is why the space complexity is of the order of n.
And as we discussed, the time complexity is of the order of n into two to the power n.