Given a sorted array of N elements, I need to find the absolute sum of the differences of all elements.Given 4 elements (1, 2, 3 and 4):|1-2|+|1-3|+|1-4|+|2-3|+|2-4|+|3-4| = 10Here is my code in Java:List<Integer> a = new ArrayList<Integer>(); //just for understanding , the Array List is already filled with numbers public static int lsum(int N){    int sum =0;    for( int i=0;i<N;i++)    {        int w =a.get(i);        for(int j =i;j<N;j++)        {            int z = a.get(j);            sum =sum +(z-w);        }        }    return(sum);}I'm looking for an efficient algorithm rather than the trivial one I am using (O(n2) complexity). This is a requirement for a bigger program which requires this function. The input (number of elements) can be as big as 105.
Simplify function to sum the absolute value of the difference between all pairs of elements of a sorted array
java;algorithm;complexity
Let's see this mathematically. I am assuming that a is an ascendingly sorted array. I start with indexes from 1, to get better readability (by avoiding n-1 as often as possible).We want the following sum:$$\begin{array}{l@{}l@{}l@{}l}\sum_{i=1}^{n-1} \sum_{j=i+1}^n (a_j - a_i) = (a_2 - a_1) &+ (a_3 - a_1) &+ (a_4 - a_1) + & \dots + (a_n - a_1) +\\                    &+ (a_3 - a_2) &+ (a_4 - a_2) + & \dots + (a_n - a_2) +\\                                &&+ (a_4 - a_3) + & \dots + (a_n - a_3) +\\                                            &&& \dots\end{array}$$So, we:add a1 zero times, a2 once,... ak k-1 times, andsubtract a1 n-1 times, a2 n-2 times,... ak n-k times.I'd say that your sum is$$\sum_{k=1}^n (k-1)a_k - \sum_{k=1}^n (n-k)a_k = \sum_{k=1}^n (2k-n-1)a_k$$Given your example (1,2,3,4), we get:$$\sum_{k=1}^4 (2k-4-1)a_k = -3 \cdot 1 + (-1 \cdot 2) + 1 \cdot 3 + 3 \cdot 4 = -3 - 2 + 3 + 12 = 10.$$This has a linear complexity, which is optimal, because you need to visit each member of the array at least once (which is linear).I believe you can write your code by yourself. Just set indexes to go from zero, but be careful about the formula: 2k - n - 1 becomes 2k - n + 1 when k starts from zero.