Computational complexity of clustering algorithms 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!
Single linkage clustering is almost the same as minimum spanning trees in complete graphs, easy O(n^2) time. For O(n^2) time for other agglomerative clustering methods (including I'm pretty sure average and complete linkage) see my paper "Fast hierarchical clustering and other applications of dynamic closest pairs", SODA '98 and JEA '00.