<p>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.</p>

CC BY-SA 2.5
2011-01-12T17:25:54.323Z
2011-01-12T17:25:54.323Z
David Eppstein
<p>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. </p>

<p><strong>Update</strong>: 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. </p>

CC BY-SA 2.5
2011-01-12T17:45:45.763Z
Why is it "not meaningful"?  There are several recent papers on the number of iterations until k-means converges (meaning an iteration leaves the clustering unchanged), or until it reaches some desired approximation ratio.
Jeffε
CC BY-SA 2.5
2011-01-12T18:36:42.093Z
but they assume either some property of the data, or some specific variant of the algorithm (like the k-means++ method, or the smoothed variant). The question as I read it seemed to refer more to generic variants. Your point is well taken though.
Suresh Venkat
CC BY-SA 2.5
2011-01-12T17:01:22.527Z
2011-01-12T18:37:39.550Z
2011-01-12T18:37:39.550Z
Suresh Venkat
<p>My wish is to describe the time complexity of several clustering approaches. For example, suppose we have $n$ data points in $m$ dimensional space. </p>

<p>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</p>

<ul>
<li>hierarchical clustering (HC) using Ward's linkage</li>
<li>HC using complete linkage</li>
<li>HC using average linkage</li>
<li>HC using single linkage </li>
<li>$k$-medoid approach</li>
<li>$k$-means approach</li>
</ul>

<p>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?</p>

<p>Thank you for your help!</p>

CC BY-SA 2.5
2011-01-12T16:07:28.497Z
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 http://area51.stackexchange.com/proposals/5120/practical-algorithms-and-data-structures .
whuber
CC BY-SA 2.5
2011-01-12T17:31:57.063Z
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)
Andrew D. King
<lg.learning><clustering>
Computational complexity of clustering algorithms
Lan
# Computational complexity of clustering algorithms

(Asked by: username_0 on 2011-01-12)

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!

**Tags:** lg.learning, clustering

> **Comments:**
> **username_1**: 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 http://area51.stackexchange.com/proposals/5120/practical-algorithms-and-data-structures .  
> **username_2**: 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)  

---

## 2 answers

### Answer by username_3 on 2011-01-12. Score: 7

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.


---

### Answer by username_4 on 2011-01-12. Score: 6

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.

> **Comments:**
> **username_5**: Why is it "not meaningful"?  There are several recent papers on the number of iterations until k-means converges (meaning an iteration leaves the clustering unchanged), or until it reaches some desired approximation ratio.  
> **username_4**: but they assume either some property of the data, or some specific variant of the algorithm (like the k-means++ method, or the smoothed variant). The question as I read it seemed to refer more to generic variants. Your point is well taken though.  

---

