0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Colm Bhandal Aug 9 '15 at 17:51
  • $\begingroup$ $\binom{i}{i} = 1$, so the sum is equal to $N + 1$. I think you've probably made a mistake in your analysis. $\endgroup$ – Peter Taylor Aug 9 '15 at 17:53
  • $\begingroup$ @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. $\endgroup$ – Dean Aug 9 '15 at 18:08
  • $\begingroup$ @ColmBhandal Yes, correct. I added the complete pseudocode for clarity's sake (and because the previous formula was wrong) $\endgroup$ – Dean Aug 9 '15 at 18:09
  • $\begingroup$ 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? $\endgroup$ – Colm Bhandal Aug 9 '15 at 18:13
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Colm Bhandal Aug 13 '15 at 13:00

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.