minimum difference between any pair in given array

Question

Given an array of n elements, what is the worst case time complexity to find minimum difference between any pair in given array?( 

1.   O(log n)
2.   O(nlogn)
3.   O(n)
4.   O(n2)
    

Comments

@gatemission try for 21,19,11,22

---

agreed @saurabh rai... i was wrong there. Thanks for counter example.

---

^correct ans is Ω(nlogn)
   nd question is not proper......if see acc 2 given options it may b O(n²) or O(nlogn)
 

Answer 1

Anser will be O(nlogn),   for any number it will give minimum differnece either with the number  which is just higher to it or just lower to  it and and have no benefit to check any number with all other number ( waste of iteration ).  

And if you sort the array , then it will fulfill our requirements,   for any ith number the number which is just greater then equals to it will be present on (i + 1 )th position and one which is just lower and equals to it is at position ( i - 1 ).

Pseudo code :

sort(arr , arr + n )             // 0 indexing based array

int res = infinite  ;

for(int i = 1 ; i < n ; ++i )  res = min( res ,  arr[i] - arr[i - 1] )

return res;    

Complexity  :  (nlogn + n )  = o(nlogn)  

As sorting also can be done in linear time with hashing( counting sort )  but they are asking for worst case , then we can assume sorting complexity to nlogn.

Hence  option 2 is correct : O(nlogn)

Answer 2

N logN is easy to find.

But not sure whether can be made better than that.

Comments

i was able to get O(n²)

whats is your method for nlogn??

---

@AkritiSood Sort in O(nlogn), then traverse the array to find minimum difference. After sorting minimum difference pair will be adjacent elements in the array. So O(nlogn) + O(n) = O(nlogn)

---

yeaa.thats correct..thankyou so much

---

Yes after sorting, min diff. between any two pairs will be between two consecutive elements.. So O(n) to scan and find min diff.and store min in some variable and then output it.