Given a simulation with formula_11 particles with a homogeneous particle density, the number of cells formula_12 is proportional to formula_11 and inversely proportional to the cut-off radius (i.e. if formula_11 increases, so does the number of cells). The average number of particles per cell formula_15 therefore does not depend on the total number of particles. The cost of interacting two cells is in formula_16. The number of cell pairs is proportional to the number of cells which is again proportional to the number of particles formula_11. The total cost of finding all pairwise distances within a given cut-off is in formula_18, which is significantly better than computing the formula_19 pairwise distances naively.