urgent recheck

[yashchou...@gmail.com]

i think there is a problem as we know 4+3+2+1 is 10 but by using formula we are getting n*n-1/2 4*3/2=6 whcih is incorrect i guess the correct formula would be n*n+1/2 kindly cehck it

[yashchou...@gmail.com]

[yashchou...@gmail.com]

answer must not be 40 it must be 60 as 1+2+3+4+5 is equals t 15

[Akarsh K]

No buddy, That's not the right way as you thought.

Question : We distribute the 20 objects into bins of equal size. How many bins should we choose to make the least number of comparisons overall? 

Answer : Since the bins should be of equal sizes. It can contain either 2 bins with 10 objects or 4 bins with 5 objects or 5 bins with 4 objects or 10 bins with 2 objects. So when u use the formula 1/2 * N * (N/K - 1) where N is the total objects and K be the number of bins. Then u get answer as 10 for 10 bins with 2 objects in each of the 10 bins.

Hope you get it. The formula is clearly shown in  L4.3: Importance of binning to reduce number of comparisons in nested iterations at 10:30.min.

[Akarsh K]

So same when u use the formula 1/2 * N * (N/K - 1) where N is the total objects and K be the number of bins. Then u get answer as 40 for 4 bins with 5 objects in each of the 4 bins.  So N = 20, K = 4 so 1/2*20*(20/4 - 1) = 1/2*20*(5-1) = 1/2*20*4 = 40

[yashchou...@gmail.com]

got it. thanks for your support

[Akarsh K Aku]

GREAT

[Computational Thinking Support 2]

Hi,

I think you have not understood the question correctly. We need to find here the number of bins which will have less number of comparisons.

In the question there are 20 objects given. So the possible number of equal size bins are 1, 2, 4, 5, 10, 20 and the corresponding size of bins will be 20, 10, 5, 4, 2, 1 respectively.

We can exclude the bin sizes of 1 (will have 20 elements which is actually question itself) and 20 (in this case there will be only one element per bin so there will not be possible any comparisons).

So now we have bins : 2, 4, 5, 10 and their size (elements) : 10, 5, 4, 2.

So no of comparisons will be 90, 40, 30 and 10 for bins 2, 4, 5 and 10 respectively.

So, clearly for bin of 10 there are10 comparisons which least among them. So the answer will be 10.

Regards,

Deepak

IITM Online Degree Team

[Yash Choudhary]

Thank you for the clarification.