Suppose we run the K-means clustering algorithm on a one-dimensional dataset, i.e. $p = 1$, so that each observation consists of a single real number.
We assume that these real numbers are distinct.
We need to show that the algorithm terminates in at most $n^{K-1}$ steps.
I know that I can find an upper bound for the number of steps based off of Stirling numbers, but that will be much higher than the required bound.
Any ideas on how to get the $n^{K-1}$ ?
Let us call our one-dimensional dataset $X$.
Since this is a deterministic algorithm that visits partitions of $X$ into consecutive data points, it suffices to show that there are at most $n^{K-1}$ such partitions.
How many such partitions of $X$ are there?
As many as there are ways to place $n$ indistinguishable balls into $k$ non-empty labelled boxes: \begin{equation} {{n+k-3} \choose {k-1}}. \end{equation}
The result follows from a direct evaluation for $k \leq 3$ and the well-known $$ {a \choose b} \leq \Big(\frac{ea}{b} \Big)^b $$ upper bound on binomial coefficients for $k \geq 4$.
