Hi, is there any efficient techniques to do the following summation ?

Given a finite set $A$ containing $n$ integers $A=(x_1,x_2,…,x_n)$, where $x_i$ is an integer. Now there are $n$ subsets of $A$, denoted by $A_1, A_2, ... , A_n$. We want to calculate the summation for each subset, i.e., $b_i=\sum_{x_j \in A_i} x_j$.

Are there some efficient techniques to compute all the values of $b_1,..., b_n$ ?

  • $\begingroup$ This is too easy. And it is really a CS question. Ask on StackOverflow if you can't figure it out yourself. Plus, as stated, in the worst-case, one can't do better than $O(n^2)$, unless you know that each of the $A_i$ are uniformly bounded in size (by a constant). $\endgroup$ – Jacques Carette Apr 30 '12 at 12:33
  • $\begingroup$ If the same sets are to be preserved, and just the values change, you might consider dataflow analysis and common subexpressions. This is only if the computation pattern is to be repeated often enough to pay for the analysis. Gerhard "Ask Me About System Design" Paseman, 2012.04.30 $\endgroup$ – Gerhard Paseman Apr 30 '12 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.