Clearly, since there are at most n points pi and steps s(tj), the whole process takes O(n log n).