Find the worstcase complexity of the hierarchical clustering

Find the worst-case complexity of the hierarchical clustering algorithm below. You may assume that the distance function takes (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 Single HClust 2 heap Min Heap 3 for 1 to n do 4 for j F i 1 to n do Insert distance (data il, datalik) into heap, along with its corresponding i and j 6 end 7 end 8 u Union Find (n) 9 count n 10 while count c do 11 (i,j, dist) heap. DeleteMin0 if then 12 uf Union 2, J 13 count count 1 14 15 end 16 end 17 return uf

Solution

Assuming input, output and distance function are taking constant
time that is their complexity is O(1) in binary operations then the:-

Insert function in double for loops takes - O(logn) * O(n^2){for double loops}

Union function at end takes - O(logn)

Union and find function in while loop takes - O(logn) * O(1){for find function} * O(n){for while loop}

Overall complexity will be the simple addition of above complexities!
Good luck!