retagged by
7,457 views
0 votes
0 votes

. 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 ?

 

  1. O(nlgn)
  2. O(n^2)
  3. Runtime is independent of n.
  4. O(log n)
retagged by

1 Answer

1 votes
1 votes

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. 

Related questions

2 votes
2 votes
1 answer
1
rsansiya111 asked Dec 8, 2021
834 views
Suppose we do merge sort with a three-way split: divide the array into 3 equal parts, sort each part and do a 3 way merge.What would the worst-case complexity of this ver...
0 votes
0 votes
3 answers
3
0 votes
0 votes
1 answer
4