edited by
432 views
1 votes
1 votes
Given a set of n distinct numbers, determine the smallest four numbers in this set using comparisons?

How much comparisons will be needed?

 

My Answer is -> (n-1)+O(lgn)
edited by

2 Answers

Best answer
1 votes
1 votes

total comparisions =(n-1)+O(lgn).

selected by
2 votes
2 votes

using min heap

  • construct min heap using build heap -------->o(n).
  • delete root node you will get first smallest ......>o(logn).
  • again delete root node you will get second min ------->o(logn)
  • again delete root node you will get third min ------->o(logn)
  • again delete root node you will get forth min ------->o(logn)

  • total comparisions  =n+o(logn)
edited by

Related questions

2 votes
2 votes
2 answers
1
iarnav asked Mar 30, 2018
1,088 views
The minimum number of comparisons required to find the minimum and the maximum of 101 numbers is ________.When n is even then it's relatively easy, but how to deal with n...
2 votes
2 votes
1 answer
2
yes asked Oct 6, 2015
1,326 views
for example array contain a[1 2 3 3 3 3 3 4 5] then retun(1)
0 votes
0 votes
2 answers
3
dhruba asked Jun 5, 2023
1,088 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...
0 votes
0 votes
1 answer
4
radha gogia asked Mar 7, 2016
707 views
How many key comparisons are there , what is the lower bound and upper bound ? For calculating the lower bound , should we consider the case when the keys are all in non-...