Consider the following problem Does a given input set of n i

Consider the following problem. Does a given input set of n integers {x1, x2, . . . , xn}, contain three elements that sum to zero? In the search version of the problem, the correct output is a set of three indices {i, j, k} such that xi + xj + xk = 0 if such a set exists, and “No” otherwise.

Show that by sorting the input, you can speed up your algorithm to obtain an algorithm that runs in O(n 2 log n) time.

Solution

Let us refer the array as A. Now after sorting let us refer the array as B. The algorithm will run as follows:

for(i=0;i<n;i++)
{
   for(j=i+1;j<n;j++)
   {
   k = binary_search(B,-1*(B[i]+B[j]));
   if(k>=0)
   {
   print(i,j,k)
   }
   }
}

The run time of this algorithm is n^2 for the two loops and logn for binary search. So the total time will be O(n^2 logn).