1
$\begingroup$

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.