The Gateway to Computer Science Excellence
+2 votes
141 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??

in Algorithms by Veteran (117k points) | 141 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??

+2
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[0] with A[1] then A[1] with A[2] 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
+1

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)

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,650 questions
56,242 answers
194,294 comments
95,947 users