USA: +1 (725) 712-1730 
Sign in
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.
