Изменения

На втором шаге алгоритма в каждой группе оболочка ищется за <tex>O(m \log m)</tex>, общее время - <tex>O(r m \log m) = O(n \log m)</tex>. На третьем шаге поиск каждой следующей точки в каждой группе занимает <tex>O(\log m)</tex>, так как точки уже отсортированы, и мы можем найти нужную бинпоиском. Тогда поиск по всем группам займет <texdpi="130">O(r \log m) = O(\frac{n / }{m } \log m)</tex>. Всего таких шагов будет <tex>k</tex>, значит общее время - <texdpi="130">O(k n / \frac{kn}{m } \log m)</tex>.Итоговое время - <tex>O(n (1 + \frac{k / }{m}) \log m)</tex>. Несложно видеть, что минимум достигается при <tex>m = k</tex>. В таком случае сложность равна <tex>O(n \log k)</tex>.