2
$\begingroup$

Is there already a worst case time complexity proof for the sum of all elements in a power set? I would assume, naively, you have to just add everything, which would run in about 2^n, where n is the size of the set.

For example: A = {1,2,3} Powerset(A) = {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3} } Sum(Powerset(A)) = {{} + {1} + {2} + {1 + 2} + {3} + {1 + 3} + {2 + 3} + {1 + 2 + 3} }

I'm defining addition between sets as: A = {1}, B = {2,3}, A + B = {1} + {2 + 3} = 6

$\endgroup$
  • 3
    $\begingroup$ Hint: how many times does $2 \in A$ appear in Powerset($A$)? $\endgroup$ – Austin Buchanan Mar 12 '14 at 5:32
3
$\begingroup$

Hint: If I understand you correctly, you are after $$ \sum_{B \subseteq A} \sum_{x \in B} x. $$ Try reversing the order of summation: $$ \sum_{B \subseteq A} \sum_{x \in B} x = \sum_{x \in A} \sum_? x, $$ where $?$ is some condition that you will have to come up with. See if that helps you to find a closed formula for the original double sum.

| cite | improve this answer | |
$\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.