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

Question

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 > ();
            newsubset.addAll(subset); //
            newsubset.add(item);
            moresubsets.add(newsubset);
        }
        allsubsets.addAll(moresubsets);
    }
    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:
        6.1 subset_of_subset.add(last_element)
        6.2 power_set_of_set.add(subset_of_subset)
    7. return power_set_of_set

Answer 1

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