title: How do I know how long will an algorithm (e.g. k-means) take to run?
body: <p>For example, I'm running the k-means algorithm on 1 million data points.  Each point is 128-dimensional, and I want 1000 clusters. Wikipedia tells me that its complexity is n^(dk+1)log(n), where d is the number of dimensions, k number of clusters and n number of instances. 
  Knowing that, how can I get an estimate of how long it will run on my 8-Gb RAM, 2.6GHz Intel Core i5 MacBook Pro?  What is the best way to calculate this estimate? Is there a way to calculate it theoretically or should I do a few experiments on smaller sets and see how long it takes?<br>
  I would really like to have rough estimate before I spend hours or days without knowing when it might stop.
  Thanks so much for your help! I really appreciate it :).</p>
  
  <p>Ps. I'm using pythons' scipy kmeans</p>