# 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? – greybeard Mar 4 at 7:38
• The total number of elements in all sets together is $n2^{n-1}$. – Yuval Filmus Mar 4 at 11:25
• @YuvalFilmus Sure, I get that. But how can we formally analyze algorithm above to get the same? – Holmes.Sherlock Mar 4 at 17:11
• @DavidRicherby I came up with a quick pseudocode – Holmes.Sherlock Mar 4 at 17:22
• @Holmes.Sherlock Thanks! – David Richerby Mar 4 at 17:33

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}$$.