 respectively if the \(l^2\) or \(l^1\) norm is considered.</li>
</ol>
<p>A naive implementation of the assignment step requires \(O(dnK)\) operations, where \(d\) is the dimensionality of the data, \(n\) the number of data points, and \(K\) the number of centers. Updating the centers is much cheaper: \(O(dn)\) operations suffice to compute the \(K\) means and a slightly higher cost is required for the medians. Clearly, the bottleneck is the assignment computation, and this is what the other K-means algorit