# Run time analysis of the clustering algorithm (k-means)

I was reading some notes on ML and clustering and it claimed that the run time of clustering was O(kn) where k is the number of clusters and n is the number of points.

I was wondering why this was true and if someone had an analysis for it.

This is what I have thought so far though:

Recall the clustering algorithm.

1) Initialize centroid $z^{(i)}, ..., z^{(k)}$

2) Repeat the following two steps until there is no further change in cost:

a) For each fixed centroid $z^{(i)}$, choose a optimal clustering such that point $x^{(i)}$ is closest to the current centroid.

b) For a fix cluster, re-compute the current centroids: $z^{(j)} = \frac{\sum_{i \in C_{j}} x^{(i)}}{|C_j|}$

We know that clustering does not run forever because of the convergence proof. So it doesn't run forever. Now, step a) takes O(kn) worst case because for each centroid $z^{(i)}$, we have to compute the Euclidean distance to each data point $x^{i}$ and choose the min one and assign it to that cluster which in the worst case we do O(n) to compute min for each centroid k. So O(kn) (I know we can use heaps or whatever, thats not what interests me). Now on the next step we compute the new means which worst case takes O(k+n) which is less than O(kn) so step b) doesn't really contribute anything to the runtime. However, Basically...how do we know that it won't keep doing this for a lot more times? How is it that the notes imply that it converges in O(1). That part was not clear to me. If its clear to anyone else, feel free enlighten me!

• Please be more precise. Clustering (see Wikipedia) is a task such as "classification", not an algorithm. It appears that you refer to a single iteration of Lloyds/Forgys algorithm for finding a local minima of the k-means problem. Mar 8 '14 at 19:18
• maybe my naming was not the official one or whatever, but I gave an outline of the exact algorithm I am talking about (i.e. I define exactly what I mean by clustering algorithm). You can point out what the name of the accepted name by the ML community for the algorithm I gave if you want. Also, if I am not more precise is because the notes I am reading are not more precise and I apologize for the notes I am reading. Mar 8 '14 at 23:18
• I updated the title, is that a better name for what I mean for "clustering algorithm"? I agree being more precise can help searching for future users. Feel free to add a more precise naming if you feel it might help. :) Mar 8 '14 at 23:26
• Well, the algorithm is attributed to Lloyd and Forgy; it isn't MacQueens k-means. The point is, this runtime does not hold e.g. for DBSCAN, or hierarchical linkage clustering. Mar 9 '14 at 15:39

Looking at these notes time complexity of Lloyds algorithm for k-means clustering is given as:

O(n * K * I * d)

n : number of points
K : number of clusters
I : number of iterations
d : number of attributes


My gut feeling is that in your case number of iterations (and number of attributes) is assumed to be constant.

• odd that they would say I is O(1). I don't really see why a theoretical reason/justification for it to be O(1). I don't even see why I is not exponential as a matter of fact. I wonder if this algorithm is in P... Mar 8 '14 at 23:27
• @Pinocchio: please clarify your comment. exponential in what? Are you claiming that the number of iteration depends on $n$, $K$ or $d$? Mar 9 '14 at 11:45
• What I mean is that, to my understanding, I have not seen any justification for why I cannot be exponential with respect to anything. i.e. I don't see why I should be polynomial with respect to any of the other variables. Mar 9 '14 at 18:56
• By accident I found in wikipedia some of the shortcomings of the k-means and in one of them it says: it has been shown that the worst case running time of the algorithm is super-polynomial in the input size. en.wikipedia.org/wiki/K-means%2B%2B Mar 10 '14 at 18:22
• @Pinocchio Here is paper that you might find useful: theory.stanford.edu/~sergei/papers/kMeans-socg.pdf Mar 10 '14 at 19:15