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
  • 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, 2018 at 7:58

1 Answer 1

9
$\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}. $$

$\endgroup$
0

Your Answer

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

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