Problem 3: (31 points) Consider the following algorithm computing the distance b

Question

Problem 3: (31 points) Consider the following algorithm computing the distance between two closest points in a given finite set of points on the plane. function MINDISTANCE(array Points 1..n]) min-distance infinity for i from 1 to n do for j from i + 1 to n do if the distance between Pointsli] and Pointsi] is less than min distance then min-distance the distance between Points[i] and Points[ end if end for end for return min distance end function Find an expression for the number of operations performed by the algorithm of the form (nk), where n is the size of Points array and k is some number.

Explanation / Answer

Here in this function, there are 2 loops , outer loop from 1 to n an dinnnter loop from outerloop+1 to n. So, for every iteration in outer loop, i , inner loop is getting executed O(N-i) times. So, total time complexity can be given as

T(N) = /theta(N-1) + /theta(N-2) + ..... + /theta(1) = /theta((N*(N-1))/2) == /theta(N^2). So, k is 2

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.