Arrays

Question

Consider an array contains 2k distinct elements. How many comparisons are needed to find the smallest and the second smallest elements in the given array?

1.  2k comparisons
2.   2k-2 comparisons
3.   2k + k -2 comparisons

Answer 1

To understand easily we take an example for any k.(here i assumed k=2)

Now we have 4 distinct elements.

No of comparisons to get smallest of them = 3

Now to get second smallest we need to compare  between the elements that are compared with smallest element.

Here 2 and 3 are compared with smallest element.

So 1 comparsion among them ==>Total = 4 comparisons.

For $2^{k}$ elements we need $2^{k} + k - 2$ comparisons.

Comments

Nice Explanation :)

$2^k -1 $ for smallest and $k -1$ for $2^{nd}$ smallest.

---

Thanks mcjoshi,

in general that is correct even for finding 2nd smallest element and 1st smallest element individually :)