Comparisons.

The Gateway to Computer Science Excellence

+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)

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,157 answers

193,767 comments

93,746 users