2
$\begingroup$

Given array $A$ of size $n$, we want to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$. Is there way to speed this up rather than the standard $O(n^3) $ calculation with 3 for loops. I haven't worked with sums so I don't know their properties, but I was thinking if there is some way to rewrite the formula to get faster calculations.

$\endgroup$
  • 1
    $\begingroup$ Use distributivity, e.g. something like $A_i B_1 + A_i B_2 + \ldots = A_i (B_1 + B_2 + \ldots)$. Try solving first a similar sum with only two indices. I think this should work. $O(n)$ should be enough. $\endgroup$ – chi May 15 '18 at 7:58
8
$\begingroup$

Let $A = \sum_{i=1}^n A_i$. We have $$ \begin{align*} A^3 &= \sum_{i=1}^n A_i^3 + 3\sum_{i=1}^n \sum_{j \neq i} A_i^2 A_j + 6 \sum_{i < j < k} A_i A_j A_k \\ &= \sum_{i=1}^n A_i^3 + 3 \sum_{i=1}^n A_i^2 (A - A_i) + 6 \sum_{i < j < k} A_i A_j A_k. \end{align*} $$ This gives a linear time algorithm.

More generally, the theory of symmetric polynomials ensures that every symmetric polynomial can be computed in linear time, since it is a polynomial in the quantities $B_d := \sum_{i=1}^n A_i^d$. For example, $$ \sum_{i<j<k} A_i A_j A_k = \frac{B_1^3+2B_3-3B_1B_2}{6}. $$

| cite | improve this answer | |
$\endgroup$

Your Answer

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

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