= One-dimensional K-means iteration bound
{title2=$N_{\mathrm{steps}}\le\binom{n-1}{K-1}\le n^{K-1}$}
For $n$ distinct observations on the real line and $1\le K\le n$, nearest-centre assignment produces contiguous blocks of the sorted observations because each <Voronoi cell> is an <interval>. The <arithmetic means> of distinct ordered blocks are strictly ordered, preserving this property at subsequent assignments. Initialize at $K$ distinct observed values so that the initial assignment has no empty cluster.
The empty-cluster repair in <finite termination of K-means clustering> also preserves contiguous blocks: an observation farthest from a centre over its assigned block lies at one of that block's endpoints, so transferring it to a new singleton splits the block into two contiguous blocks.
There are $\binom{n-1}{K-1}$ possible partitions into $K$ nonempty blocks: choose $K-1$ cuts among the $n-1$ gaps. Under the stable tie rule in <finite termination of K-means clustering>, every round after the first strictly reduces the objective until stopping, so a block partition cannot recur. The number of assignment, repair, and centre-update rounds is therefore at most $\binom{n-1}{K-1}\le n^{K-1}$. Check stability after each update without an additional update round; for $K=1$, one update suffices.
Back to article page
