What is the time and space complexity of single linkage hierarchical clustering?

I have read everywhere that the time complexity of hierarchical agglomerative clustering is $$\mathcal{O}(n^3)$$ and it can be brought down to $$\mathcal{O}(n^2 \log n)$$.

How do we arrive at such conclusions? Could you please provide to me a detailed derivation of these time complexities?

I think the space complexity should be $$\mathcal{O}(n^2)$$, because, for $$n$$ data items, we need a matrix with $$n^2$$ "locations", and hence it is $$O(n^2)$$. Am I right?

Single linkage can be done in O(n) memory and O(n²) time.

See the SLINK algorithm for details. It does not use a distance matrix.

• single link does not use distance matrix ?? this are the steps for single link clustering ..en.wikipedia.org/w/…... here its written that to update the proximity matrix after every merge l.. Commented Jun 3, 2017 at 15:52
• Wikipedia does not explain the more efficient algorithm, but the easiest (but slower). Commented Jun 3, 2017 at 21:03
• ok , sir thanks a lot . I have read the improved Slink algorithm proposesd by R Sibson which takes time complexity of O(n2) and space complexity O(n).. i have understood the time complexity case .At each of O(n) iterations it takes O(n) time and hence the compelxity is O(n2). But how are we getting the space complexity as O(n). Because atleast once we need to create the dissimilarity matrix which needs O(n2) space . Am i right or again i have mistaken ? Commented Jun 4, 2017 at 19:57
• No, where does it generate a dissimilarity matrix? Every distance is computed and used exactly once. Commented Jun 4, 2017 at 21:04
• dear sir , i am really confused .. will you please give the steps in simple words ... then it will be very helpful for me .. Commented Jun 5, 2017 at 9:34

It depends on the implementation. For distances matrix based implimentation, the space complexity is O(n^2). The time complexity is derived as follows :

• Distances matrix construction : O(n^2)
• Sorting of the distances (from the closest to the farest) : O((n^2)log(n^2)) = O((n^2)log(n))
• Finaly the grouping of the items is done by iterating over the the sorted list of distances : O(n^2)

=> overall time complexity = O(n^2) + O((n^2)log(n)) + O(n^2) = O((n^2)log(n))