doubt regarding reduction factor

[Vishakh Agarwal]

sir

i want to know that while we calculate the reduction factor in the bin concept , why dont we take into consideration those comparisons that were made while we were binning objects .

For EXAMPLE,

if we  bin 1000 objects into 10 bins of equal size, the number of comparisons within  those bins =49,500,ie, 10*(100*99)\2.

the number of comparisons to bin the items into the 10 bins ranges from [1000,10000] when we use the if-else if concept.

Therefore, 

We need to add the two 49500+[1000,10000].

Without binning, the total comparisons are 4,99,500

HENCE, the reduction factor in this case should not be 10 in the real sense but less than it since the denominator is greater than 49500.

please help me out

[Anand Iyer]

Visakh,

What's the logic behind [1000, 10000] number of comparisons, to fit 1000 items into 10 bins?  Why should you do more than comparison to fit each item into a bin?  I'm not clear on that.

[Vishakh Agarwal]

WE WANT TO BIN 1000 OBJECTS INTO 10 BINS...FOR THAT WE NEED TO DO ONE ITERATION WHEREIN WE NEED TO COMPARE EACH OF THOSE 1000 OBJECTS WITH A SUITABLE CONDITION TO BIN THAT OBJECT INTO A PARTICULAR BIN. THERE WOULD BE 10 CONDITIONS, ONE FOR EACH BIN.

SO, THE MINIMUM NUMBER OF COMPARISONS THAT MIGHT BE REQUIRED TO BIN OBJECTS WOULD BE 1000 AND MAXIMUM WOULD BE 10000...CONSIDERING THE FACT THAT WE USE IF- ELSE IF STRUCTURE FOR COMPARING WITHIN THE ITERATION.

I HOPE NOW U WOULD BE ABLE TO CONNECT WITH MY QUESTION....AND THANKYOU FOR REPLYING

[Anand Iyer]

ah, got it now.  

what you're saying is right. 

Now, when we speak about searching using a binning strategy, we don't include the binning process itself into this.  Thus, the reduction factor obviously doesn't consider this.

If you ask why should we not include it, I don't have a clear answer.  Maybe, our tutors can pitch in?

--

Cheers,

Anand

[Vishakh Agarwal]

YES..THANK YOU

 

Sent from Mail for Windows 10

[Computational Thinking Support 2]

Hi Vishakh,

I got your point and the points made by Anand is connect. I want to add something in that.

When we create bins we compare the element with the chosen or decided range/criteria not between the elements. So the comparisons between the elements and the comparisons done to create bins are different. The total number of comparisons after binning include only the comparisons between elements within each bins not the comparisons done to create the bins. Yes, we need to write some extra code in the program to create the bin.

So, we count only the comparisons between the elements not the comparisons done to create bins.

Hope your doubt is cleared if not please write us again.

Regards,

Deepak

IITM Online Degree Team