Modified GATE-2014 Comparisons

Question

Minimum number of comparisons to find minimum and maximum of 100 numbers ??

Average number of comparisons to find minimum and maximum of 100 numbers ??

Maximum number of comparisons to find minimum and maximum of 100 numbers ??

Find all the 3 cases in detailed manner which should work for all inputs.

Comments

Someone expain this

---

to know the element which u selected u have to traverse the entire list other wise u will not know it as minimum...so to get maximum or minimum..the minimum number of comparisons will be n-1 for the n elements as u need to compare that one element to all the other n-1 elements

Answer 1

1)minimum no of comparisions use

min heap tree minimum element only '1' comparision-----if we use max heap ,find max element is only '1' comparision

3)maximum element 100 comaprisions in min heap tree.(we don't know where max element present)

minimum element 100 comparisions in max heap tree.

2)for average no of comparisions use avl tree.

min and max element requires log(100)+1=8 comparisions.

3)we can search max element in only '1' comparision using max heap tree.

if we consider constructio for tree also it requires o(nlogn)=100*log(100)=700.

no of comparisions   =700+cost for searching particular element(max or min)

finally prefer binary search tree(avl tree) to search any element in only o(logn) comparisions

Comments

to design min heap itself take O(n).after that it take 0 comparision to get 1st minimum.

---

you should not use different data structure to find min and max 

Take one and find min and max of 100 numbers then evaluate numbers of comparisions involved ....

https://gateoverflow.in/1917/gate2014-1_39