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
• $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?

• This is a CS question, not a question about statistical analysis. It would be perfectly suitable for the SE site on algorithms currently in the proposal stage at area51.stackexchange.com/proposals/5120/… . Commented Jan 12, 2011 at 16:07
• You can also transform the distance matrix into an edge-weighted graph and apply graph clustering methods (e.g. van Dongen's Markov CLustering algorithm or my Restricted Neighbourhood Search Clustering algorithm), but this is more of an OR question than a straightforward algorithms question (not to mention that graph clustering algorithms are generally unsuitable for dense graphs, which kind of defeats the purpose of turning the distance matrix into a graph) Commented Jan 12, 2011 at 17:31

You have to be careful with some of the methods. Specifically, k-means and k-medoids are iterative schemes that you run "till you're done". SO it's not meaningful to talk about the overall running time of these schemes, but it is meaningful to talk about the running time of a single iteration. For $k$-means, it's easy: each iteration takes $O(kn)$ time to identify the nearest centers and do the new center computation. For $k$-medoids, the new-center computation can take longer: that depends on what procedure you use, and if $k$ is small, the computation of new-centers can dominate the asymptotics.
Update: As JeffE points out below in comments, there are certain variants of $k$-means that do have guaranteed convergence in polynomial time, while also yielding quality answers. There's nothing that I'm aware of for $k$-medoids though.