title: What is the time complexity of k-means?
body: <p>I was going through the <a href="http://en.wikipedia.org/wiki/K-means_clustering" rel="noreferrer">k-means Wikipedia page</a>. Based on the algorithm, I think the complexity is <code>O(n*k*i)</code> (<code>n</code> = total elements, <code>k</code> = number of cluster iteration)</p>
  
  <p>So can someone explain me this statement from Wikipedia and how is this NP hard?  </p>
  
  <blockquote>
    <p>If <code>k</code> and <code>d</code> (the dimension) are fixed, the problem can be exactly solved in time <code>O(n<sup>dk+1</sup> log n)</code>, where <code>n</code> is the number of entities to be clustered.</p>
  </blockquote>