What is the efficient solution for computing the sum of all pair sum square in an array?

Question

Given an Array $A[0\cdots n-1]$ we need to compute $\sum_{i = 0}^{n-1}\sum_{j=0}^{n-1}\left((A[i] + A[j]) imes (A[i] + A[j]) ight)$ . What is the running time of a time-efficient solution?

I thought the running time of the time-efficient solution for the equation

$S=\sum_{i = 0}^{n-1}\sum_{j=0}^{n-1}\left((A[i] + A[j]) imes (A[i] + A[j]) ight)$

would be n^2 (quadratic time) but the solution is n (linear time).

Can someone explain me how is it n (linear time)?

user_3768871 · Answer

Just you need to rewrite the formula. The inner formula is $(A[i] + A[j])\times (A[i] + A[j]) = A[i]^2 + A[j]^2 + 2 A[i]A[j]$ . Hence, you can take out $A[i]$ from the inner sum:

$\sum_{i = 0}^{n-1}\left(n imes A[i] + \sum_{j = 0}^{n-1}\left(A[j]^2 ight) + 2A[i] imes \sum_{j = 0}^{n-1}\left(A[j] ight) ight)$

Now just we need to compute $B= \sum_{j = 0}^{n-1}(A[j]^2)$ , $C = \sum_{j = 0}^{n-1}(A[j])$ , and $\sum_{i = 0}^{n-1}(n imes A[i] + B + 2A[i] imes C)$ . As each of them can be done in O(n), we can find the final result in O(n).

Notice that, you can do it in O(n^2) by two nested loops (as you said). But it is not optimized. You can find similar techniques in matrix multiplication (Strassen algorihtm) as well.

What is the efficient solution for computing the sum of all pair sum square in an array?

1 Answers