Madeeasy

Question

Consider a procedure find ( ) which take array of n integers as input and produce pair of elements of array whose difference is not greater than the difference of any other pair of element of that array. Which of the following represent worst case time complexity of find ( ) procedure?
 

I am not getting what this question want to ask, Does it want pair with smallest difference.

Also do elements in pair need to be adjutant to each other?

It will really helpful if explained with small example

Comments

please someone answer this question

---

given answer is 

But i think better explanation will be as follow:

Instead of findings pairs whose difference is not largest , let's find pair whose difference is largest.

We can use divide and conquerer procedure of merge sort and find pair/s with highest difference , this can be done O(nlogn) time. Once we found this pair/s rest of all pairs are one which have difference less than this maximum distance.

---

https://gateoverflow.in/87823/stack-overflow

Answer 1

TIME COMPLEXITY IS O ( n log n) by sorting the elements in ascending order by merge sort and fiding out the pairwise differences with time complexity O (n).

hence the time complexity is O (n).