Proof of sum of powerset? 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
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.