Log In
25 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)$
in Algorithms
edited by

You should post this as the answer

Reference ->

On above link take a look on Mcdowella's explanation.

We need to use stable sorts like Merge sort ... Correct me if i am wrong ...

5 Answers

35 votes
Best answer

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.

edited by
Gradient will be max , when y2-y1 will be max , why are u not considering this fact??
Himanshu1 is right. Rather than comparing x distances we should compare slope of consecutive points. Otherwise for example (1,1), (2,2), (4,10) will give us wrong answer. Although I don't know how to prove this.
does it work for cordinates (1,1) (2,3) (4,8) (6,9)

it remains same after sorting
then we get min difference of x cordinates at (1,1) (2,3)
We get slope of 2

But highest slope is for (2,3) (4,8) which is 2.5??
Yeah we should compare both x and y values so above solution is not correct. @Arjun Sir can u help in this one?
shouldn't we find gradient of all the points and then sort them up.

bcoz, gradient depends on both X & Y values.
x coordinate and y coordinate both will be arrange in ascending or descending order ,it will take o(n(logn))..

now find minimum of (Xi+1 - Xi) and maximum of (Yi+1 - Yi) (it will take 0(n)) then slope will be maximum

so total time = 0(n(logn)) + 0(n)

to solve and understand this type of question , what kind of basic information need to know or necessary ,

bcoz of i am nothing able to understand this question and answer.,  this question what saying,?

anyone can help.,
Why will it take o(n) to find min difference... As we already sorted the points.. Should be o(1)

@shubham shende 

actually we need to check if any two point gives diferredif "0" ( x- coordinates ) so that gradient will be "infinity" , for that we need O(n).

I have a basic doubt, if we want the gradient to be minimum, then we want x2-x1 as max, so instead of sorting entire array in nlogn time, why can't we take the max and min values of x which will take O(n) time, then difference between this max and min x value will always be max. Similarly we can get first 2 min elements of Y in O(n) time. What crucial part I'm missing I'm not getting

I went through the mentioned links however it didn't help to solve this query.

Thanks in advance
Why max and min values of x? We want x1 and x2 to be as close as possible, so we have to sort it first, then find minimum difference between consecutive points.
6 votes
B) arrange the x coordinates in ascending order and then find the smallest difference between the neighbours.
Y coordinates also matter in slope. (y2-y1/x2-x1)
4 votes
I think D, for each and every pair we have to check.
To see 3 points are linear or not, we can do binary search.
then we have to find theta.
3 votes

Answer is well explained in this link:

option B

3 votes

Related questions

33 votes
3 answers
Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compute $b^n \bmod{m}, 0 \leq b, n \leq m$ ? $O(\log n)$ $O(\sqrt n)$ $O\Biggl (\frac{n}{\log n} \Biggr )$ $O(n)$
asked Oct 30, 2014 in Algorithms Ishrat Jahan 3.8k views
32 votes
10 answers
A depth-first search is performed on a directed acyclic graph. Let $d[u]$ denote the time at which vertex $u$ is visited for the first time and $f[u]$ the time at which the DFS call to the vertex $u$ terminates. Which of the following statements is always TRUE for all edges $(u, v)$ in the graph ? $d[u] < d[v]$ $d[u] < f[v]$ $f[u] < f[v]$ $f[u] > f[v]$
asked Oct 30, 2014 in Algorithms Ishrat Jahan 4.7k views
26 votes
1 answer
Consider a weighted, undirected graph with positive edge weights and let $uv$ be an edge in the graph. It is known that the shortest path from the source vertex $s$ to $u$ has weight 53 and the shortest path from $s$ to $v$ has weight 65. Which one of the following statements is always TRUE? Weight $(u,v) \leq 12$ Weight $(u,v) = 12$ Weight $(u,v) \geq 12$ Weight $(u,v) > 12$
asked Oct 30, 2014 in Algorithms Ishrat Jahan 3.7k views
31 votes
5 answers
Consider the $B^{+}$ tree in the adjoining figure, where each node has at most two keys and three links. Now the key $K50$ is deleted from the $B^+$ tree resulting after the two insertions made earlier. Consider the following statements about the $B^+$ tree resulting after ... (i) and (ii) are true Statements (ii) and (iii) are true Statements (iii) and (i) are true All the statements are false
asked Oct 31, 2014 in Databases Ishrat Jahan 5.4k views