What is the complexity of the following algorithm which is similar to the nearest neighbour?

Question

What is the time complexity of the following algorithm?

Input: set of points P and their Euclidean coordinates

1. Compute a tour of the points (using the nearest neighbour algorithm, like in the TSP problem)

2. For each point, get the nearest neighbour info (with respect to all points in the original data set)

Is the complexity O(n) or O(n²)? How can we easily visualize complexity and efficiency?

Answer 1

1. 1. For each point, you have to find the nearest neighbor. (you get the first n)

   2. Computing the distance between two points get you a factor 1, because it runs in O(1).

   3. So, computing the distance between one point and all the other points gets you a factor O(n).

   In total you get O(n²). Sure, in step 3 you do not have to compute the distance to visited points, but this saves only a constant factor.

2. The nearest neighbor info of a point A is the nearest point to A. So you have to compute for n points the distance to all other points, so you get here also O(n²)

Adding this together results in O(n² + n²) = O(2n²) = O(n²).