The Gateway to Computer Science Excellence

+3 votes

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??

0

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[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)

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

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??

+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??

+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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,832 questions

57,686 answers

199,273 comments

107,208 users