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 & Time complexity of it?

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


1 Answer 1



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:

  1. draw a random sample
  2. perform one iteration of k-means using this sample
  3. repeat

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.