Find the worst-case complexity of the hierarchical clustering algorithm below. Y

Question

Find the worst-case complexity of the hierarchical clustering algorithm below. You may assume that the distance function takes Theta (1) time to compute. Input: data: set of data points Input: n: size of data Input: distance: distance function that takes two data points and returns a nonnegative real number Input: c: desired number of clusters; must be an integer between 1 and n Output: single-linkage hierarchical clusters for data 1 Algorithm: SingleHClust heap = MinHeap() for i = 1 to n - 1 do for j = i + 1 to n do Insert distance(data[i], data[j]) into heap, along with its corresponding i and j end end s uf = UnionFind(n) count = n while count > c do n (i, jf, dist) = heap.DeleteMin() if ti.Find(i) uf.F'md(j) then if.Union(i, j) count = count - 1 is end end return uf

Explanation / Answer

The above algorithm has a nested loop starting at line 3 and a while loop at line 10. In this scenario, the worst case time complexity is sum of time complexities for both loops. Notice that both these loops are dependent on n , the size of input.

In general, for a m-level nested loop, the time complexity is O(nm). In our case, the nesting is 2. So the time complexity for nested loop at line 3 is O(n2) . For the plain loop at line 10 without nesting, the time complexity is O(n). Together the worst case time complexity is O(n2)+O(n) =O(n2+n)

-------

Please do rate the answer if it helped. Thanks

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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