Пусть N — количество частиц, (равномерно) расположенных в пространстве,
Nb — количество потенциальных контактов частицы i (например, соседних частиц), Nb<<N,
Nc — количество реальных контактов частицы i, Nc<=Nb
NС — общее количество контактов между частицами в системе, NC = SUM(Nc)/2

Как рассчитать сложность алгоритма, определяющего NC?

В простейшем случае надо проверить на контакт все N(N-1)/2 потенциальных пар => сложность алгоритма расчета NC будет O(N^2).

Если теперь для частицы i определить Nb, тогда для нахождения Nc для этой частицы надо проверить только Nb(Nb-1)/2 потенциальных пар.
А как теперь оценить сложность нахождения полного NC?
Я думал, что так как всего N частиц, и на каждую по Nb(Nb-1)/2 проверок, => N*Nb(Nb-1)/2 всего проверок => O(N*Nb^2).
Но для частицы j, находящейся в потенциальном контакте с частицей i надо проверить уже на Nb-1 соседей меньше, а для частицы k, находящейся одновременно в контакте c обеими частицами i и j, проверять надо уже Nb-2, и т.д. Как это учитывать? Может быть тогда имеем (N/Nb)*Nb(Nb-1)/2 всего проверок? и сложность O(N*Nb)?