# Complexity of subset-generation algorithm

I'm trying to calculate the computational complexity of an algorithm which generates the power set of a set of items.

The algorithm works using the recursive formula of the binomial coefficient

$$\binom nk = \binom{n-1}{k-1} + \binom{n-1}k$$

Any result of $$\binom{n-1}k$$ is appended (so this is O(1)) but the results of $$\binom{n-1}{k-1}$$ need to prepend an element of the set to each result (and this takes time proportional to the result).

As an example: the power set for the set 1,2,3 is as follows:

 for k from 0 to 3 (the set's size)
calculateSubsets(set, k);

calculateSubsets(set, k)
{
el = take the first item from the set (set is now one element less)
append_result(calculateSubsets(set, k));
other_result = calculateSubsets(set, k-1);
for each item in other_result
item = el + item // Prepend el to the item
append_result(other_result)
}


since appending it's done in constant time, I suppose the bulk of the work (proportional to the input) is the prepending of the set's item.

Can somebody help me out with calculating the bound for this recursion?

• When you say you are computing the power set, are you actually generating a data structure in memory that is of size $2^n$, where $n$ is your original set size? Aug 9 '15 at 17:51
• $\binom{i}{i} = 1$, so the sum is equal to $N + 1$. I think you've probably made a mistake in your analysis. Aug 9 '15 at 17:53
• @PeterTaylor the prepending operation is probably the bulk of the work but I got it wrong with the previous writing. I'm editing the last part of the message. Let me know if this is somewhat clearer.
– Dean
Aug 9 '15 at 18:08
• @ColmBhandal Yes, correct. I added the complete pseudocode for clarity's sake (and because the previous formula was wrong)
– Dean
Aug 9 '15 at 18:09
• OK I'll take a look. Immediately though I think you might be asking something a bit different from "computational complexity"- is it recursion depth you want? Aug 9 '15 at 18:13

Let's say we have an array of size $2^n$. At each position in the array we store a representation of a subset by:
Each index in the array, written in binary, represents the subset in question. Then we can generate all subsets with complexity $2^n$ by stepping through the array, and at each point pointing to one element in the original set and one lower element in the array (representing the remaining set). Since this is $2$ operations per iteration, which is constant, we achieve the complexity $2^n$.
• On reflection, I would have to advise against using this for any practical application. Because traversing through each subset's elements is no more efficient than simply creating the subset on the fly from a binary representation. In other words, what I'm saying is, there's no point in storing all the subsets (at least not that I can see). You can just represent subsets as binary numbers, where the index of each digit represents the element and the value $1/0$ represents in/out respectively. Aug 13 '15 at 13:00