2
$\begingroup$

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$ ?

$\endgroup$
2
  • $\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$ Apr 30, 2012 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$ Apr 30, 2012 at 15:09

0

Your Answer

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

Browse other questions tagged or ask your own question.