T(c(n/2)) и T(f(n/2)) описывают, сколько времени требуется для рекурсивного вызова алгоритма в левой и правой группах соответственно, поскольку половина точек была размещена в каждой группе.
O(n) происходит из хитрой части алгоритма: после рекурсивных вызовов мы нашли δ, а именно расстояние между ближайшей парой точек либо в левой группе, либо в правой группе. Теперь мы хотим найти пары, состоящие из одной точки из левой группы и одной точки из правой группы. Конечно, мало смысла смотреть на точки, которые находятся дальше, чем δ от средней линии. Тем не менее, все еще может быть, что все точки находятся в пределах δ от средней линии, поэтому, похоже, мы рискуем сравнить n^2 пар точек. Важное наблюдение сейчас заключается в том, что именно потому, что мы знаем, что в каждой группе ни одна пара точек не ближе, чем δ, мы знаем, что существует небольшой постоянный предел для худшего случая, сколько точек из правой группы нам нужно посмотреть для каждой пары в левой группе. Поэтому, если мы можем отсортировать наши точки только по их y-координатам, мы можем найти ближайшую пару за линейное время. Этот отсортированный список можно получить за линейное время из-за способа передачи списка между рекурсивными вызовами, но детали меня избегают (не стесняйтесь заполнять, любой).