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:
- Compute the median of x-coordinates of all point, and divide the plane into two half Left, and Right.
- Recursively do 1. then when there is only 1 point, rank(that point)=0.
- Sort points by y-coordinate in Left, and Right separately.
- 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.