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
$ $ T(n)=2T(n/2)+\Theta(n),$ $
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.