Question

Python 3: Part B needed

Write a function "closest_pair" to determine the closest pair in Theta(N^2) time, return that pair as a tuple. The closest pair is defined as the pair of numbers whose difference is the minimum of all pairs in the list. For example:

Given the list [ 3,6,4,10,23] the closest pair would be (3,4) since the difference is just 1.

Given the list [10, 45, 55, 42, 20], the closest pair would be (42,45) since the different is just 3

Given the list [4,10,6,7,10,5], the closest pair would be (10,10) since the distance is zero.

B) Write a function "fast_closest_pair" to determine the closest pair (same as in part A), except this time you should do it in better than Theta (N^2).

Answer 1

Hello, I am putting the code for Both A as well as B. Where I put the comment also for your better understanding where first program is taking O(n*n) time complexity and second will take O(n*log n) time complexity. which is better than first one. Although you have any doubt, feel free to comment down and if you like my answer, don't forget to give me upvote.

Thank you, Enjoy your answer.

# Answer : A)

mylist = [4,6,10,7,10,5];

tuplee = (mylist[0], mylist[1])
minimum = abs(mylist[0] - mylist[1])


# this loop will take O(n)
for i in range(0, len(mylist)-1):
        # below loop also will take O(n) times
        # As It is using nested loop 
        # So here complexity will be multiplied.
        # so complexity = O(n)* O(n) = O(n^2)
        for j in range(i+1, len(mylist)):
                a = mylist[i]
                b = mylist[j]
                if(minimum > abs(a-b)):
                        minimum = abs(a-b)
                        tuplee = (a, b)
print("using n*n time complexity: ",tuplee)

Now Second Program:

mylist = [4,6,10,7,10,5];


# this will take O(n*logn)
mylist = sorted(mylist)

tuplee = (mylist[0], mylist[1])
minimum = abs(mylist[0] - mylist[1])

tuplee = (mylist[0], mylist[1])

# this will take O(n), but it is not using nested loops
# so, here Complexity will added.
# so complexity = O(n*log n) + O(n) = O(n*log n)
# which means this is better than first one
for i in range(1,len(mylist)):
        a = mylist[i-1]
        b = mylist[i]

        if(minimum > abs(a-b)):
                minimum = abs(a-b)
                tuplee = (a, b)
print("using n*log n time complexity: ",tuplee)

Hope You understood this answer.