What is the computational complexity of K-Means?

K-Means complexity is O(n × k × i × d), where n is data points, k clusters, i iterations, and d dimensions.

Each iteration computes distance from every point to every centroid. This scales linearly with dataset size but can become expensive for large n, k, or d. Optimizations include vectorization, KD-trees (limited usefulness), and mini-batch K-Means.