Complexity of subset-generation algorithm

Question

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?

Answer 1

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:

1. A pointer to some element in the original set.
2. A pointer to a lower index in the array (which is the remaining set)

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