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]).
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”.
for i in range(len(pairs)):
for j in range(i+1,len(pairs)):
#just comparing with squares, no need of rooting
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.