TIFR CSE 2011 | Part B | Question: 31

Question

Given a set of $n=2^{k}$ distinct numbers, we would like to determine the smallest and the second smallest using comparisons. Which of the following statements is TRUE?

• A. Both these elements can be determined using $2k$ comparisons.
• B. Both these elements can be determined using $n - 2$ comparisons.
• C. Both these elements can be determined using $n + k - 2$ comparisons.
• D. $2n - 3$ comparisons are necessary to determine these two elements.
• E. $nk$ comparisons are necessary to determine these two elements.

Comments

What is $\mathbf k$ here?

Is it the $\mathbf 2$ elements which we need to compare finally?

Or is it just the representation?

---

elements are in 2 POWER k

---

WATCH THIS  FOR BETTER UNDERSTANDING CLEARLY EXPLAINED ALL THESE TYPE OF PROBLEMS 

Answer 1

Option (c) $n+k-2$

Here is a nice explanation of the algorithm: http://www.codinghelmet.com/?path=exercises/two-smallest

it is solution to the problem known for ages, and it has to do with tennis tournaments. The question was, knowing the outcome of the tennis tournament, how can we tell which player was the second best? The defeated finalist is a good candidate, but there are other players that were defeated directly by the tournament winner and any of them could also be a good candidate for the second best. So the solution to the problem is quite simple: Once the tournament finishes, pick up the $\log N$ competitors that were beaten by the tournament winner and hold a mini-tournament to find which one is the best among them. If we imagine that better players correspond with smaller numbers, the algorithm now goes like this. Hold the tournament to find the smallest number (requires $N-1$ comparisons). During this step, for each number construct the list of numbers it was smaller than. Finally, pick the list of numbers associated with the smallest number and find their minimum in $\log N-1$ steps. This algorithm requires $N+\log N-2$ comparisons to complete, but unfortunately it requires additional space proportional to N (each element except the winner will ultimately be added to someone’s list); it also requires more time per step because of the relatively complex enlisting logic involved in each comparison. When this optimized algorithm is applied to example array, we get the following figure.

Tournament held among numbers promotes value $1$ as the smallest number. That operation, performed on an array with nine numbers, requires exactly eight comparisons. While promoting the smallest number, this operation has also flagged four numbers that were removed from competition by direct comparison with the future winner: $6, 2, 3$ and $8$ in that order. Another sequence of three comparisons is required to promote number $2$ as the second-smallest number in the array. This totals $11$ comparisons, while naive algorithm requires $17$ comparisons to come up with the same result.

All in all, this algorithm that minimizes number of comparisons looks to be good only for real tournaments, while number cracking algorithms should keep with the simple logic explained above. Implementation of simple algorithm may look like this:

a – array containing n elements  
min1 = a[0] – candidate for the smallest value  
min2 = a[1] – candidate for the second smallest value
if min2 < min1
    min1 = a[1]
    min2 = a[0]
for i = 2 to n – 1
    if a[i] < min1
        min2 = min1
        min1 = a[i]
    else if a[i] < min2
        min2 = a[i]

by Zoran Horvat @zoranh75

Comments

why not B? n-2 comparisons means we will pick the 1st element and compare it with all elements from 2nd to (n-1)th element.Now even if we didn't compare it with last element,we would be sure that the element is either smallest or second smallest.Now remove that element,put the last element in its place.Again we select 1st element and this time we compare till the last element thus getting the smallest one(or second smallest).

---

@Arjun Sir Can u tell why it is taking log n comparison. In program I am not getting any loop which is going i=1 to n/2. So, why log N?

---

@shikhar That means n-2+ n-3 = 2n-5 rt?

@srestha See the last part of the code- We compare with min1 in if. Now, consider the condition for elseif. This is not very clear - but this is executing $\log a$ times for $a$ distinct values.

---

ok I misread it, it is n-2 comparisons each for smallest and second smallest element.

---

I am not getting in terms of k..

(3n/2)-2

---

@srestha mam

the implementation given is not of the tennis tournament algo.It is a normal algo in which we are first comparing first 2 elements to get first and second minimum respectively.

Then, we are checking the remaining (n-2) elements ,to see if they are candidates for first and second mini or not.

Overall the implementation does ::

1 comparison ( to initialize min1 and min2) +

2*(n-2) comparisons (In worst case , we could need 2 comparisons for each of the n-2 remaining elements , to suitably update min1 and min2)

Total time complexity = 1+ 2(n-2)

PS:: The above time complexity is not of the tennis tournament but the implementation code given above.

For more clarity you may read http://www.codinghelmet.com/?path=exercises/two-smallest

,from where the example as been taken.

---

Thanks VS :-)

---

Can anyone explain more clearly in simple words?

---

@rajatmyname check this https://gateoverflow.in/27194/tifr2014-b-9

 

---

We can build min heap in log n => (k) and the smallest element can be extracted in O(1) time.

Now again min-heap can be created in log n => (k) steps which will give the overall second smallest element.

so the time taken will be approx 2k

Am i missing something ?

---

@jinal99: Building a heap takes O(n) time, not O(log n)

Can you extract the minimum of an unsorted array in less than O(n) time? Definitely not, because you atleast need to look at each element once.

You're saying that even though extracting min takes n time, extracting both min and second min takes only log n time?

 

---

@Pragy Agarwal yes sir, my mistake, building a min-heap and extracting first smallest number = O(n) 

Again heapify and extract min will take O(log n) = k 

then total time will be approx n + k.

This approach is correct? 

 

---

Awesome question and beautiful explanation

---

Why we are not using tournament method as stated here in this question https://gateoverflow.in/1917/gate2014-1-39

And I think even here we will need (n-1) comparisons only, just like here in GATE 2014 question. https://gateoverflow.in/1917/gate2014-1-39?show=328108#c328108

Can anyone please tell me where I'm going wrong?

 

Edit: I got my mistake. The loser of the last tournament need not always be the second smallest always. We will have to conduct a mini-tournament with all the players who lost to the final winner. Number of such players who lost to the final winner = log n. To find smallest among these log n players we will need (log n - 1) comparisons.

Total comparisons to find smallest and the second smallest = (n - 1) + [(log n) -1] = n + log n - 2

Hence C is the answer. :)

---

How many comparisons are required to find third minimum?

I think it is $loglogn - 1$.

By applying above tennis tournament method, third minimum can be obtained by conducting a tournament with all the players who were defeated by the second minimum. There will be $loglogn$ players who lost with second minimum. Hence comparisons are $loglogn - 1$.

Edit: Above answer is wrong.

$1,4,2,3,5,6,7,8$ is one possible example where the above method fails to find third smallest element.

Why tournament method isn't able to find the third smallest element?

How to find comparisons required to find third smallest element?

---

here we need to compare the players defeated by SECOND min and first min both

---

Tournament method says it requires $2N – 1$ comparisons. Here the ans is $n + logn – 2$, how?

---

Tournament method for finding second smallest??

---

The above method is Tournament method, isn’t it?

---

No @neel19 if we apply naive algorithm then it would take 2n-1 comparisons when we apply tournament method then it would take n+logn-2

Answer 2

Second smallest of n elements can be found with n+ceil(lg n)-2 comparisons in worst case .This result is present in exercise question of CLRS book Edition 3 chapter 9 - Medians and Order Statistics

First we do n-1 comparisons to find first smallest among n element.Now there are lg(n) element left who lost to first smallest element.Take lg(n) element find second smallest element in lg(n) -1 comparisons.Note:For finding second smallest we need to find first smallest.

Total comparisons=n-1+lg(n)-1=n+lg(n)-2

ATQ

n=2^k distinct number 

Use above result n+lg(n)-2=n+lg(2^k)-2=n+k-2

So c is ans.

 

Comments

@himanshu26 ,Thanks !, but , My doubt is how to implement in program to save these lost elements ?, like how to get that 8,2,4 are defeated ?

---

Gfg have algorithm for this. Refer:

https://www.google.com/amp/s/www.geeksforgeeks.org/second-minimum-element-using-minimum-comparisons/amp/

---

In the question, it is mentioned that all values are distinct and the size of the array is of the order of  $2^k$. This will yield the same type of complete binary tree for any value of $k$. If we do a heapify then we can get the smallest element with an $n-1$ number of comparisons. Next, for finding the second smallest number we just have to do one more comparison with the children of the root element. Therefore, the total number of comparisons will equal to $n – 1 +1 = n$ according to me.

Please let me know if there is any fault with this argument.

Answer 3

this can be done by OPTION ELIMINATION too

let us assume k=5 for all cases (n=32)

 

a.) 2k = 10

if array is already sorted(descending order) , then smallest will be last , so WRONG

 

b.)n-2=30

same explaination as above , bcz to find smallest and 2nd smallest, each cell is compared TWICE . WRONG

 

e.)nk = nlogn

that is merge sort , thus this is NOT the Optimal as it sorts the array too . WRONG

 

d.)2n-3 = 2(n-1)-1

these number of comparison will be MORE than suffice , assume min=A[0] and min_2 =A[0] , compare min and min_2 with remaining cells (ie n-1 cells) twice (WRONG bcz option says NECESSARY , which is not true)

 

c.) n+k-2 = n+logn -2

this is the BEST OPTION

build min heap =O(n)

extract Min = O(log n)

then compare the 2 elements after removing min

Answer 4

For the problem of finding minimum and second minimum, there is a better algorithm based on tournaments. Here we compare A[2i−1] with A[2i] for i = 1 to n. (We assume for simplicity that n is even.) We compare the ”winners” in pairs and so on. For example, see the diagram below:

The light blue cells are those that lost to the final winner (in green). The red are those that lost to the light blue ones and dark blue is one that lost to a red. So for the second minimum we need only compare the light blue ones. There is exactly one of these per level and there are log n levels and hence we get a total of n + log n − 2 comparisons in all.