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
Proof of sum of powerset?
complexity theory;time complexity