Let P1,P2,…,Pn be n points in the xy-plane such that no three of them are…
2007
Let P1,P2,…,Pn be n points in the xy-plane such that no three of them are collinear. For every pair of points Pi and Pj, let Lij be the line passing through them. Let Lab be the line with the steepest gradient among all n(n−1)/2 lines.
The time complexity of the best algorithm for finding Pa and Pb is
- A.
Θ(n)
- B.
Θ(n log n)
- C.
Θ(n log² n)
- D.
Θ(n²)
Attempted by 8 students.
Show answer & explanation
Correct answer: B
Sort the points by their x-coordinate. For any two non-adjacent points Pi and Pj in this sorted order, the slope of the line joining them is a weighted average of the slopes of the consecutive segments between them. Therefore, it cannot be larger than all of those adjacent slopes.
So the steepest line must be formed by two adjacent points in x-coordinate order. The algorithm is:
1. Sort all n points by x-coordinate: Θ(n log n).
2. Scan each adjacent pair, compute its slope, and keep the maximum: Θ(n).
Total time = Θ(n log n) + Θ(n) = Θ(n log n).
Hence, the best algorithm for finding Pa and Pb has time complexity Θ(n log n).