What is the Space & Time Complexity of Mini-Batch K-Means clustering algorithm? For vanilla K-Means clustering algorithm I know that the time complexity is:


  Time complexity: O(tknm),


where n is the number of data points, k is the number of clusters, and
t is the number of iterations, m is the dimensionality of the vectors. 

So, when I studied about Mini-batch K-Means to make the algorithm converge faster, I wanted to find out what is the Space &amp; Time complexity of it? 

Essentially so that I understand well, how much we are optimizing over vanilla K-Means.
Infinite.

Mini-batch k-means never converges, you need to use an iteration limit or similar heuristic, and you can never guarantee to have found a local optimum.

In essence, mini-batch k-means is:


draw a random sample
perform one iteration of k-means using this sample
repeat


Assuming that your sample size is N, 2 takes O(k N m t) time.