Computational Complexity of K$-$Means

$1$ point possible $($graded$)$

Remember that the K$-$Means algorithm is given by

Randomly select $z_1,$dots,$z_K$

Iterate

Given $z_1,dots{z}_K,$ assign each $x^{(j)}$ to the closest $z_j,$ so that

Cost$(z_1,dots{z}_K)={\displaystyle \underset{i=1}{\overset{n}{}}}mi{n}_j=1,$dots,$k||x^{(i)}-z_j|{|}^2$

Given $C_1,$dots,$C_K$ find the best representatives $z_1,$dots,$z_K,$ i$.$e$.$ find $z_1,$dots,$z_K$ such that

$z_j=\frac{{\displaystyle \underset{iE{C}_j}{\overset{?}{}}}{x}^{(i)}}{|C_j|}$

Assuming that there are $n$ data points $\{x_1,$dots,$x_n\},K$ clusters and representatives, and each

$x_{i}in\{x_1,$dots,$x_n\}$ is a vector of dimension $d,$ what is the computational complexity for one complete

iteration of the k$-$means algorithm? That is$,$ find the time $($or the number of steps$)$ it takes to complete steps $2\mathrm{.}1$

and $2\mathrm{.}2.$

Note on Big$-$O notation

$O(n)$

$O(nK)$

$O(n{K}^2)$

$O(ndK)$