How much work does binning save?

For a bin containing nᵢ items, the pair count is nᵢ(nᵢ−1)/2. Add that number over all bins. This works even when the bins are not the same size.

If k bins have exactly equal sizes n/k, the sum simplifies to n(n/k−1)/2. Compared with n(n−1)/2, the exact reduction factor is (n−1)/(n/k−1), provided the denominator is nonzero. This is about k for large bins. Equal-size formulas require equal counts, not merely equal-width ranges.

Three checks before you use bins #

First, prove that excluded cross-bin pairs cannot matter for an exact search. Second, inspect the actual bin sizes: uneven distribution changes the saving. Third, include the cost of grouping and storage. Physical bins take desk space; computer bins take memory. Memory is large but not unlimited.

If every bin has at most one card, there are zero within-bin pair checks. Do not divide by zero to call the speedup a finite factor. You still had to read and place the cards. Creating thousands of empty bins may also waste space; using only bins that occur can be helpful.