Find Median of Array of pairwise difference of an array

Revision en1, by purist, 2018-07-18 00:50:53

Given an array, we can generate an array which stores all the pairwise absolute difference of elements of original array. How can we find median of this new array. For example : A = {1,2,3,4} then we can generate difference array as G = {1,1,1,2,2,3} then median is 1.can it be done in better than quadratic time? Also what if we don't take absolute value of difference?

Tags #algorithms, median

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English purist 2018-07-18 00:50:53 425 Initial revision (published)