My wish is to describe the time complexity of several clustering approaches. For example, suppose we have $n$ data points in $m$ dimensional space.
Suppose further that the pairwise dissimilarity matrix $\Delta$ of $n\times n$ dimensions is already computed and that we have already spent $O(m\cdot n^2)$ steps. What is then the time complexity just of
- hierarchical clustering (HC) using Ward's linkage
- HC using complete linkage
- HC using average linkage
- HC using single linkage
- $k$-medoid approach
- $k$-means approach
Is there any benefit if the dissimilarity matrix $\Delta$ is not already computed? As I understand it is necessary for HC and $k$-medoid approach but not for $k$--means?
Thank you for your help!