Algorithm $4\mathrm{.}1$ k$-$means algorithm: given a list of N n$-$vectors x$1,,$ xN $,$ and an initial

list of k group representative n$-$vectors z$1,,$ zk repeat until convergence

$1.$ Partition the vectors into k groups. For each vector i $=1,,$ N $,$ assign xi to the group

associated with the nearest representative.

$2.$ Update representatives. For each group j $=1,,$ k$,$ set zj to be the mean of the vectors

in group j

Complexity of k$-$mean algorithm.

$($a$)$ In step $1$ of the k$-$means algorithm, we find the nearest neighbor to each of N n$-$vectors,

over the list of k centroids. Show that this requires approximately $3$N kn flops.

Exam $1$ Page $4$ of $5$