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

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Hint: how many times does $2 \in A$ appear in Powerset($A$)? $\endgroup$
    – Austin Buchanan
    Commented Mar 12, 2014 at 5:32

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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