# What is the complexity of the algorithm to calculate power set of a set?

Below is an algorithm to compute the power set of a set. To my understanding, for a set with cardinality n, there is a for loop iterating 2^(n-1) times. Hence the time complexity has to be O(2^n).

However, the time complexity as per the solution, is O(n*2^(n-1)). What mistake am I making?

Arraylist < Arraylist < Integer >> getSubsets(Arraylist < Integer > set, int index) {
Arraylist < Arraylist < Integer >> allsubsets;
if (set.size() == index) { //Base case - add empty set
allsubsets = new Arraylist < Arraylist < Integer >> ();
allsubsets.add(new Arraylist < Integer > ()); // Empty set
} else {
allsubsets = getSubsets(set, index + 1);
int item = set.get(index);
Arraylist < Arraylist < Integer >> moresubsets
new Arraylist < Arraylist < Integer >> ();
for (Arraylist < Integer > subset: allsubsets) {
Arraylist < Integer > newsubset = new Arraylist < Integer > ();
}
}
return allsubsets;
}


The pseudocode looks like:

// set: The set[0:n-1] which the power set has to be computed for
set getSubset(set):
1. set_size = size(set)
2. set_size == 1:
2.1 return [{}, set]
3. power_set_of_subset = getSubset(set[0:set_size-2])
4. last_element = set[set_size-1]
5. power_set_of_set = power_sets_of_subset
6. for subset_of_subset in power_set_of_subset:
7. return power_set_of_set

• Can all operations in the loop be assumed to take constant time? Commented Mar 4, 2019 at 7:38
• The total number of elements in all sets together is $n2^{n-1}$. Commented Mar 4, 2019 at 11:25
• @YuvalFilmus Sure, I get that. But how can we formally analyze algorithm above to get the same? Commented Mar 4, 2019 at 17:11
• @DavidRicherby I came up with a quick pseudocode Commented Mar 4, 2019 at 17:22
• (If you want to use singular in the pseudocode, I'd vote for powerset or getPowerset.) Commented Mar 4, 2019 at 17:38

The running time of step 6 depends on the size of subset_of_subset.
The reason is that the final list needs to contain both the original subset and the subset with last_element added to it. This requires copying the subsets, which takes time linear in its size.
Consequently, the running time of the algorithm scales at least as the total size of all subsets, which is $$n2^{n-1}$$.