edited by
545 views
1 votes
1 votes
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 array. which of the
following represent worst case time complexity of find() procedure?
a. O(n)
b. O(log n)
c. O(nlog n)
d. (n^2 log n)
edited by

2 Answers

0 votes
0 votes
First of all we need to sort the element which takes O(n*log(n)) .

Then take a variable min_diff=a[1]-a[0].

Perform a O(n) time operation on this sorted array that compares the difference between two successive elements with the current value of min_diff and change it accordingly .

Overall complexity will be O(n*log(n)).
0 votes
0 votes
First sort the array it will take O(nlogn) time then take first n last key value its diff will be max, it will take constant time so overall complexity is O(nlogn).

No related questions found