Algorithm 4.1 k-means algorithm: given a list of N n-vectors x1, , xN , and an initial list of k group representative n-vectors z1, , 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 3N kn flops. Exam 1 Page 4 of 5