9,660 views
49 votes
49 votes

Given a set of $n$ distinct numbers, we would like to determine the smallest three numbers in this set using comparisons. Which of the following statements is TRUE?

  1. These three elements can be determined using $O\left(\log^{2}n\right)$ comparisons.
  2. $O\left(\log^{2}n\right)$ comparisons do not suffice, however these three elements can be determined using $n+O(1)$ comparisons.
  3. $n + O(1)$ comparisons do not suffice, however these three elements can be determined using $n +O(\log n)$ comparisons.
  4. $n+O(\log n)$ comparisons do not suffice, however these three elements can be determined using $O(n)$ comparisons.
  5. None of the above.

7 Answers

0 votes
0 votes
ans will be B

construct a min heap and find the smallest 3r d element is O(1)

so total time req is O(n).
0 votes
0 votes
Is is some what similar to what himanshu1 stated but calculations required are less

It can be found using TOURNAMENT APPROACH

minimum element can be found using n-1 comparison

2 nd minimum will compare with all those who lost against minimum so it contains n/2 elements

So second minimum can be found in

Log(n/2-1) comparison

Similarly third smallest can be found using Log(Log(n/4-1)) comparison

Total complexity O(n-1 +Log(n/2-1)+(log(n/2-1)+log(n/4-1)) )

Which is equal of O(n+ klogn)

k<n

C should be correct
edited by
0 votes
0 votes
Build heap will take O (n) and after that to extract 3 elements we need just log n time for each element so overall is (n+3logn)

But using selection sort it is n+(n-1)+(n-2)

 

Now of we take mathematically min heap is best
Answer:

Related questions