NPTEL Assignment Question

Question

. You are given a set of n points on the number line. They are given in arbitrary order. The task is to find the points that are closest to each other.

To solve the problem you decide to take one point and compute its distance to all other points and repeat this process for all points. During the process you track the closest pair.

What is the running time of this algorithm ?

 

• A. O(nlgn)
• B. O(n^2)
• C. Runtime is independent of n.
• D. O(log n)

Answer 1

The answer is B $O(n^2)$.

The reasoning behind this is that you essentially calculate the distance between all the pairs of points. Assuming there are n numbers, you calculate the distance (based on this algorithm) for $n \dfrac{(n-1)}{2}$ pairs, hence $O(n^2)$.

 

Since all numbers are on the number line, this can be done in a more efficient way, i.e. sort the points in the line and the traverse the list of points to find the closest.