One-dimensional K-means iteration bound ($N_{\mathrm{steps}}\le \left(\genfrac{}{}{0ex}{}{n-1}{K-1}\right)\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 $\left(\genfrac{}{}{0ex}{}{n-1}{K-1}\right)$ 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 $\left(\genfrac{}{}{0ex}{}{n-1}{K-1}\right)\le n^{K-1}$. Check stability after each update without an additional update round; for $K=1$, one update suffices.