What is Space and Time Complexity of the Hierarchical Clustering Algorithm?

Data Science, AI and ML
#1

Space complexity: Hierarchical Clustering Technique requires very high space when the number of observations in our dataset is more since we need to store the similarity matrix in the RAM. So, the space complexity is the order of the square of n.

Space complexity = O(n²) where n is the number of observations.

Time complexity: Since we have to perform n iterations and in each iteration, we need to update the proximity matrix and also restore that matrix, therefore the time complexity is also very high. So, the time complexity is the order of the cube of n.

Time complexity = O(n³) where n is the number of observations.