Using Python, please answer all the questions:)

Given in points in the plane, consider the problem of finding the pair of points that is closest together. One algorithm for doing this is the brute-force method: list all the pairs, compute their distances, and take the smallest one. (i) Explain how this brute-force algorithm can be implemented without ever computing a squareroot . (ii) Implement this algorithm in Python (without using squareroot s). Your code should accept a list of points (ordered pairs (x_i, y_i) of floats) and return the two points that are closest together. (iii) Show that this algorithm has temporal complexity in O(n^2) (where the fundamental operations include basic arithmetic operations +, -, times, /, assigning a value to a variable or to a given position in a list, looking up the value of a particular element at a given position in a list, comparing two values, and incrementing a value). Surprisingly, there is a O(n log n) algorithm for solving this problem (see [KT05, 5.4]).

## Expert Answer

**Solution=====================**

**1) Square root is not important, as we only need to know, which two points are relatively closer. Even if we stop to the of the distance formula’s step, where both x and y are squared and added. We can get away with using this “distance^2” for comparisons, rather than square rooting them to “distance”.**

**2)**

def getClosestPair(pairs):

point1=()

point2=()

smallestDistanceSq=sys.maxint

for i in range(len(pairs)):

for j in range(i+1,len(pairs)):

xDistance=pairs[i][0]-pairs[j][0]

yDistance=pairs[i][1]-pairs[j][1]

#just comparing with squares, no need of rooting

distanceSq=(xDistance*xDistance)+(yDistance*yDistance)

if(distanceSq<smallestDistanceSq):

point1=pairs[i]

point2=pairs[j]

smallestDistanceSq=distanceSq

print(point1)

print(point2)

print(smallestDistanceSq)

**3)As we can see that, the outer loop iterates for each number of pairs(N), while the inner loop also does the same. Making it N*N = O(N^2). Since the complexity of other operations(like +,- etc.) are trivial/constant to this, they as per rule, are simply discarded for** **computing time complexity.**