create pairs of vertices using adjacency list in linear time

Question

I have n number of vertices numbered 1...n and want to pair every vertex with all other vertices. That would result in n*(n-1)/2 number of edges. Each vertex has some strength.The difference between the strength of two vertices is the weight of the edge.I need to get the total weight. Using two loops I can do this in O(n^2) time. But I want to reduce the time.I can use adjacency list and using that create a graph of n*(n-1)/2 edges but how will I create the adjacency list without using two loops. The input takes only the number of vertices and the strength of each vertex.

for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++)
    {
        int w=abs((strength[i]-strength[j]));
            sum+=w;
    }

this is what i did earlier.I need a better way to do this.

@VTT they arent direct edges.two nodes are connected by only one edge — Sohit Gore
@VTT, no, it would be O(N*N) - quadratic, not exponential. — Serge Rogatch

Serge Rogatch Serge Rogatch · Accepted Answer · 2017-08-30T12:40:41

If there are O(N*N) edges, then you can't list them all in linear time.

However, if indeed all you need is to compute the sum, here's a solution in O(N*log(N)). You can kind of improve the solution by using instead O(N) sorting algorithm, such as radix sort.

#include <algorithm>
#include <cstdint>

// ...

std::sort(strength, strength+n);
uint64_t sum = 0;
int64_t runSum = strength[0];
for(int i=1; i<n; i++) {
  sum += int64_t(i)*strength[i] - runSum;
  runSum += strength[i];
}
// Now "sum" contains the sum of weigths over all edges

To explain the algorithm:

The idea is to avoid summing over all edges explicitly (requiring O(N*N)), but rather to add sums of several weights at once. Consider the last vertex n-1 and the average A[n-1] = (strength[0] + strength[1] + ... + strength[n-2])/(n-1): obviously we could add (strength[n-1] - A[n-1]) * (n-1), i.e. n-1 weights at once, if the weights were all larger than strength[n-1], or all smaller than it. However, due to abs operation, we would have to add different amounts depending on whether the strength of the other vertex is larger or smaller than the strength of the current vertex. So one solution is to sort the strengths first, so to ensure that each next strength is greater or equal to the previous.

create pairs of vertices using adjacency list in linear time

1 Answers