278 views

Consider a procedure $find()$ which take array of $n$ integers as input, and produce pair of element 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??

$A)O(n)$  $B)O(nlogn)$  $C)O(n^{2})$  $D)O(n^{2}log n)$

Here we need to sort first and then need to compare adjacent element

right??

Then what will be complexity??

| 278 views
0
yes...Time Complexity will be $O(nlgn + n) =O(nlgn)$
0

@ankitgupta.1729

which algo will be good here??Merge Sort or quick sort??

Can u tell me the algo, from where r u getting T.C. nlogn?? and not  $n^{2}$ or $n^{2}log n??$

It is asking for worst case

right??

+5
mam,  either apply merge sort or heap sort.. both will give $O(nlgn)$ running time in worst case whereas worst case running time of quick sort is $O(n^2).$

Here,  We have to find a pair of elements whose absolute difference is minimum.
Algo :-

1) First sort the elements in O(nlgn) time.
2) scan the whole array and check the absolute difference between each pair of elements. So, comparison should be like this A with A then A with A and so on. We are doing like this because if elements are sorted then only adjacent will give least difference if we scan array from left to right and elements are sorted in non-decreasing order.
This whole process of scanning takes O(n)  time to find the least difference pair of elements.

So, Total running time will be O(nlgn +n) =(nlgn)
0

@ankitgupta.1729

but why u have taken minimum among all worst case??

It is not told

rt??

0

After sorting program will be like this

max=0;
for(i=0;i<n;i++)
{
temp=a[i+1]-a[i];
if(temp>max){
max=temp;
}

}

right??

0
0
+2

but why u have taken minimum among all worst case??

I have not taken minimum..Answer can be $O(n^2)$..  I have given one algo which works better than $O(n^2)$..There might be some better algo than $O(nlgn)$ worst case running time also.

After sorting program will be like this

here we are finding min. difference..  first store the difference of first 2 elements in a variable then compare this value by the difference of further consecutive elements of this array. If you get less than that at any time then update the value of that variable..

+1

I have written the program

first store the difference of first 2 elements in a variable then compare this value by the difference of further consecutive elements of this array

I have taken it as max.

But question was O(nlogn)*O(n)

or

O(nlogn)+O(n)??

But here first we sort , then find max. difference , i.e. O(nlogn)+O(n)

right??

0
yes right..  it should be O(nlogn) +O(n) not O(nlogn)*O(n)
0
Why don't we use a O(n) sorting algorithm to sort ? In that case it would be O(n)+O(n).
+1

@srestha Please correct me -  I think first i will perform 2 times selection sort. We will get the least 2 element. Now the difference between them will be always less or equal to any possible pair in the array.

time complexity = O(n) in every case. Then why we someone go to sort the array first and find the pair.

+1

@arjun @srestha i am also getting the same doubt . why dont find the minimum and maximum element and then negative difference between them would be the ans

0
yeah it should be order of n only!