What is the Space & Time Complexity of Mini-Batch K-Means clustering algorithm?
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.