edited by
6,174 views
43 votes
43 votes

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

  1. $\Theta\left(n\right)$
  2. $\Theta\left(n\log n\right)$
  3. $\Theta\left(n\log^2 n\right)$
  4. $\Theta\left(n^2\right)$
edited by

6 Answers

Best answer
50 votes
50 votes

Answer: B

Gradient $= y_2 - y_1 / x_2 - x_1$

For gradient to be maximum $x_2 - x_1$ should be minimum. So, sort the points (in $\Theta(n\log n)$ time) according to $x$ coordinate and find the minimum difference between them (in $\Theta(n)$ time).

Best complexity: $\Theta(n\log n +n)$ which leads to B.

https://www.careercup.com/question?id=4787065684230144

https://stackoverflow.com/questions/8222108/max-slope-from-set-of-points

edited by
6 votes
6 votes
B) arrange the x coordinates in ascending order and then find the smallest difference between the neighbours.
4 votes
4 votes
I think D, for each and every pair we have to check.
Answer:

Related questions

50 votes
50 votes
3 answers
1