Comparing performance of kNN and kMeans How do they compare performance wise in speed, accuracy, sparse, dense dataset ?
Is it possible to somehow theorize what the runtime for kNN or means would be?
 A: Short answer: yes.  You could do more than theorize runtime.  You could terminate k-means based on runtime instead of the number of iterations.  So you can predict how long k-means would run down to the millisecond.  This deviates from the textbook implementation and will usually result in less accurate results compared to running for a fixed number of iterations without improvement, but it is possible to do so.
I'm not really familiar with kNN, but since it's a classifier it answers a similar but different question than a clustering algorithm like k-means.  
K-means can be re-implemented as a classifier by saving cluster centers between runs.  How useful this is depends on use case details.
Data where the class label is based on a few specific points or features in the solution space will be more accurately classified with k-means.  Data where the class label is based predominately on nearby/local features will be more quickly classified by kNN.  It's a little more complicated than saying one is better than the other for "sparse" or "dense" data.  How the class labels are determined would be important in deciding which algorithm to use.
A: kNN is a classification algorithm, while k-Means is a clustering algorithm, so you're comparing apples and oranges.
If you want to compare different types of kNN algorithms (different K or weighting), just use classification measures like % accuracy on a test dataset, F-Measure or area under ROC curve.
If you want to compare different versions of k-Means or other clustering algorithms, you may use the V-Measure or the quantization error. For a more comprehensive list, check this paper.
For both, speed can be measured by running the algorithms many times and computing the average time for training and, in the case of kNN, for testing. You may also want to check the time complexity for both algorithms, which does not require experimentation. KNN vs k-Means.
But if you plan to use k-Means for classification, by storing the correct label for each cluster, just treat it as classification algorithm and use the same measures you'd use for kNN.
