Arrays

Question

Consider an array of 19 elements, Find the minimum number of comparisons required to find minimum and maximum elements in an array

Comments

28?.

Answer 1

is anythng i miss?

Comments

how 9 for max ?

---

@Anirudh your explaination is clear and simple ..

But how about when given 500 elements , this perfectly time taking and not possible even.

Please solve this using reccurence relation for three cases 

 https://gateoverflow.in/79484/modified-gate-2014-comparisons

Answer 2

Minimum number of comparison is O(1) ,when we know array is sorted.

But here we donot know array as sorted

So, minimum no. comparison and maximum number of comparison=O(n)=3/2n-2 comparisons

For 19 element , in worst case it will be (3/2*19-2) comparison.

Comments

does it matter?

---

when n is odd , 1.5n-2 won't be able to produce integer so i think it matters.

---

@Rupendra

not required , see here

https://gateoverflow.in/1248/gate2007-50#c169881

Answer 3

We have to do (n-1) comparison , so for 19 elements total comparison requires is 18.

Comments

Hello vishwa , question is not about 'Min number of comparison required in best case'

It's general case in which any arrangement can be possible.

so it can't be like n-1=18