K-Means is a popular algorithm for partitioning a dataset into a pre-determined number of clusters, denoted by 'K'. The core idea is to group data points so that points within the same cluster are similar to each other, while points in different clusters are dissimilar. It achieves this by trying to minimize the variance within each cluster.

This measure of variance is called the within-cluster sum of squares (WCSS). It's the sum of the squared distances between each data point and the center of its assigned cluster. This cluster center is called a centroid. The algorithm's objective is to find the set of clusters C and their centroids $ \mu_k $ that minimize this value.

In simpler terms, we're trying to make the clusters as tight and compact as possible by minimizing the total distance of all points from their respective cluster centers.

K-Means finds these optimal clusters not through a single, complex calculation, but through a simple, iterative process. It repeats the same two steps until it finds a stable solution.

The initialization step can be as simple as picking K random data points from the dataset to serve as the first centroids. After that, the algorithm enters a loop, alternating between the assignment and update steps.

The pseudocode for this process is quite direct.

The algorithm continues this cycle of assigning points and updating centroids until it reaches a state of stability, which is called convergence. This happens when an iteration completes and one of two conditions is met:

1. The centroids no longer move.
2. The assignments of data points to clusters no longer change.

In practice, a third condition is often used: the algorithm stops after a fixed number of iterations to prevent it from running for too long on complex datasets.

Each step in the algorithm is designed to reduce the total within-cluster sum of squares (WCSS). The assignment step explicitly assigns each point to the closest centroid, which by definition minimizes the WCSS for the current set of centroids. The update step then calculates the new centroids (the means of the points in each cluster), and the mean is the point that minimizes the sum of squared distances for a given set of points. Because the WCSS can never be negative and decreases (or stays the same) with every step, the algorithm must eventually reach a point where no further improvement is possible and the process stops.

The efficiency of K-Means is one of the reasons for its popularity. Let's look at its computational complexity, which is a way to describe how the algorithm's runtime scales with the size of the input data.

Let:

• $n$ be the number of data points.
• $K$ be the number of clusters.
• $d$ be the number of dimensions of each data point.
• $i$ be the number of iterations until convergence.

In each iteration, the algorithm performs two main operations. First, in the assignment step, it calculates the distance from each of the $n$ data points to each of the $K$ centroids. This takes $O(n \cdot K \cdot d)$ time. Second, in the update step, it computes the mean for each cluster. This involves summing the coordinates of all $n$ points, which takes $O(n \cdot d)$ time.

Since the assignment step is the more computationally expensive of the two, the complexity of a single iteration is dominated by it. The total complexity is the cost per iteration multiplied by the number of iterations.

In many practical applications, the number of clusters $K$, dimensions $d$, and iterations $i$ are much smaller than the number of data points $n$. This makes the algorithm's runtime scale roughly linearly with the size of the dataset, making it very efficient for large datasets.