Given a simulation with N particles with a homogeneous particle density, the number of cells m is proportional to N and inversely proportional to the cut-off radius (i.e. if N increases, so does the number of cells). The average number of particles per cell c ¯ ¯ = N / m therefore does not depend on the total number of particles. The cost of interacting two cells is in O ( c ¯ ¯ 2 ) . The number of cell pairs is proportional to the number of cells which is again proportional to the number of particles N . The total cost of finding all pairwise distances within a given cut-off is in O ( N c ) ∈ ∈ O ( N ) , which is significantly better than computing the O ( N 2 ) pairwise distances naively.