2. Now consider algorithms based on the divide &conquer; paradigm, all using the

Question

2. Now consider algorithms based on the divide &conquer; paradigm, all using the template SMALLESTDIST(A1..n]) 11 n= return oo else if n 2 return D(A], A[2) else m |n/2] di SMALLESTDISTAI.m) do MIN(d1, d2) return CROSsDIST(A..,m, do) where CROSSDIST A[1..n], m, do) returns the minimum of do, and the smallest distance between a point in All ..m] and a point in Alm + l..nl 2a. (7p). First assume that CROSSDIST is implemented in the naive way: CROSsDIST(A1..,m, do) for i 1 to m for j m + 1 to n return d With this implementation, analyze SMALLESTDIST to give precise and simple bounds for the asymp- totic behavior of F(n) and T(n).

Explanation / Answer

2.) SD(n) = SD(n/2) + SD(n/2) + CD(n,m)

= 2SD(n/2) + O(n^2)

from Master theorem,

a=2, b=2 k =2

Since, a<b^k;

SD(n) = O(n^k) = O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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