Let $P_1, P_2,\dots , P_n $be $n$ points in the $xy$-plane such that no three of them are collinear. For every pair of points $P_i$ and $P_j$, let $L_{ij}$ be the line passing through them. Let $L_{ab}$ be the line with the steepest gradient among all $n(n -1)/2$ lines.
The time complexity of the best algorithm for finding $P_a$ and $P_b$ is
- $\Theta\left(n\right)$
- $\Theta\left(n\log n\right)$
- $\Theta\left(n\log^2 n\right)$
- $\Theta\left(n^2\right)$