Comparisons.

The Gateway to Computer Science Excellence

+9 votes

What is the complexity of finding $50^{th}$ smallest element in an already constructed binary min-heap?

- $\Theta(1)$
- $\Theta (\log n)$
- $\Theta (n)$
- $\Theta (n \log n)$

+11 votes

Best answer

It is constant.as long as number is independent of n it can be found with k×k-1/2 Comparisons.

The 50 th smallest element must be within first 50 levels of minheap.

for first min :0 comp(root itself)

For second min: 0(first min) +1 comp(at level 2) =1

For 3 rd min : 0(first min) +1(2 nd min) +2(to compare the child elements of 2nd min and the other node left at 2 nd level : 2 Comparisons for comparing 3 elements to find min )=3

Similarly

For 50th smalest=0+1+2...+49=

49*50/2=1225 Comparisons which is constant

We need not delete the elements in which case the complexity will be 50 logn

+3

The 50 th smallest element must be within first 50 levels of minheap.

for first min :0 comp(root itself)

For second min: 0(first min) +1 comp(at level 2) =1

For 3 rd min : 0(first min) +1(2 nd min) +2(to compare the child elements of 2nd min and the other node left at 2 nd level : 2 Comparisons for comparing 3 elements to find min )=3

Similarly

For 50th smalest=0+1+2...+49=

49*50/2=1225 Comparisons which is constant

We need not to delete the elements in which case the complexity will be 50 logn

for first min :0 comp(root itself)

For second min: 0(first min) +1 comp(at level 2) =1

For 3 rd min : 0(first min) +1(2 nd min) +2(to compare the child elements of 2nd min and the other node left at 2 nd level : 2 Comparisons for comparing 3 elements to find min )=3

Similarly

For 50th smalest=0+1+2...+49=

49*50/2=1225 Comparisons which is constant

We need not to delete the elements in which case the complexity will be 50 logn

+1

I have just one confusion that for the root node shouldn't it be that no of comparisons are equal to 1 , while for the second node no of comparisons are 2 since we reached that node after we compared it with the root node and then the node itself ,plz clarify me on the no of comparisons ,little confused that why didn't u consider no of comparsions for root node to be 1 ?

0

In level 1,we are comapring the min root wth two elements in the level 1,so isnt it 2 comprisons?

@Anurag

@Anurag

0

suppose heap has root=2

left child=4 and right child =6

to find 2nd smallest we need to compare only 4 and 6(only left child with right child) because root is already the smallest element.So only one comparison is needed.

left child=4 and right child =6

to find 2nd smallest we need to compare only 4 and 6(only left child with right child) because root is already the smallest element.So only one comparison is needed.

0

what is n here?

if n=50 , then 50 log 50 =300

which is not equal to 1225

Moreover , it is 50 th smallest element where we neednot go upto 50th level for binary heap.right?

if n=50 , then 50 log 50 =300

which is not equal to 1225

Moreover , it is 50 th smallest element where we neednot go upto 50th level for binary heap.right?

+1 vote

Deletion of min element from min-heap can be done in logn time. To find the 50th min element we have to perform 49 deletion of min element from the binary min-heap.

Therefore, total time to extract 50th min element = 49 lgn

= theta(lgn)

Therefore, total time to extract 50th min element = 49 lgn

= theta(lgn)

0 votes

0 votes

Finding minimum element in a min heap takes **O(1) **time. To find the 50th smallest element in a min heap needs to delete first 49 smaller elements and then finding the next smaller element, i.e. 50th smallest element.

Deleting smallest element (root element in a min heap) takes **O(logn)** time. Total time to delete 49 smaller elements is **O(49*logn) = O(logn). **Next finding the next min element takes O(1) time.

Next inserting all the 49 deleted elements need to be inserted back into the heap. That takes **O(49*logn). **The total time complexity thus becomes **O(logn).**

52,215 questions

59,981 answers

201,180 comments

94,634 users