retagged by
595 views
0 votes
0 votes
Consider a set of n distinct elements, by comparison Amit wants to find the largest 3 elements in the set. Which of the following is true

a) Three largest elements can be determined using O(log ^2 n ) comparison

b)O(log ^2 n ) comparison is not sufficient, but can be found using n comparisons

c)n + O(1) comparison are needed

d)n + O(1) not sufficient , n + O(log n) comparisons required
retagged by

3 Answers

Best answer
1 votes
1 votes

d) is correct.

1. Build a max heap with n elements --- takes O(n) time

2. Perform delete root thrice --- takes 3 + 3logn time i.e. O(logn)

So total time = O(n + logn)

selected by
0 votes
0 votes
D is correct answer.

But, B could have been the correct answer as we can apply Bubble Sort for 3 passes and get 3 largest elements.
So we’ll get  n+n+n = 3n = O(n)

But it is given ‘n comparisons’ and not O(n) therefore it is better to go for Heap Sort

So, O(n) for build heap and 3 times deletion of root and rearrangement will take 3logn

There O(n) + O(log n)

Related questions

0 votes
0 votes
0 answers
1
bts1jimin asked Sep 10, 2018
1,827 views
What is the number of comparisons required to extract 45th element of the min heap?
1 votes
1 votes
1 answer
2
thor asked Nov 23, 2016
580 views
3 votes
3 votes
1 answer
3
dd asked Nov 21, 2016
398 views
Increasing order of complexity.
1 votes
1 votes
1 answer
4
AJAY KUMAR ARYAN asked Jan 8, 2016
1,078 views
Q:- which one is the best among heap sort ,quick sort and merge sort in terms of complexity ? please answer with explanation!!