# 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. Commented Mar 8, 2014 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. Commented Mar 8, 2014 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. :) Commented Mar 8, 2014 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. Commented Mar 9, 2014 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... Commented Mar 8, 2014 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$? Commented Mar 9, 2014 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. Commented Mar 9, 2014 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 Commented Mar 10, 2014 at 18:22
• @Pinocchio Here is paper that you might find useful: theory.stanford.edu/~sergei/papers/kMeans-socg.pdf Commented Mar 10, 2014 at 19:15