Can k-means fall into an infinite loop ?

Question

I've studied the k-means algorithm and I know how it works.

Just curious,is there any situation that this algorithm will go into an infinite loop,say if we have some particular bad choices for initial centroid points? I could only imagine a situation k-means will get to local minimum with bad initial choices.

Answer 1

No. k-means has an upper bound of O(n^kd) in d-dimensional space.