I'm reading about the algorithm of finding the ranks of all points in a 2D plane, I don't understand the time complexity formula for it. It has four steps:

  1. Compute the median of x-coordinates of all point, and divide the plane into two half Left, and Right.
  2. Recursively do 1. then when there is only 1 point, rank(that point)=0.
  3. Sort points by y-coordinate in Left, and Right separately.
  4. Update Right.

I understand the idea of these steps, and 3. has complexity $O(n\log n)$, but the time complexity formula in my book is


why the last term is not $\Theta(n\lg n)$? That is my current idea is that the $T(n)=\Theta(n\lg^2n)$, by applying master's theorem.


1 Answer 1


I think I may solve it but I'm not sure: In short the sorting can be done in $\Theta(n)$, so the book statement, hence my assumption, is not correct. The "Sort points by y-coordinate in Left, and Right" actually only need to merge it, and this step is $\Theta(n)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.