Why Clustering Important:
Unsupervised, discovers hidden structure without labels. Uses: customer segmentation, gene grouping, image segmentation, anomaly detection, document clustering, feature engineering, data compression.

K-means Algorithm Steps:

Input: Data $X=\{x_i\}_{i=1}^n$, $k$, distance (Euclidean)
Goal: minimize $J=\sum_{j=1}^k\sum_{x_i\in C_j}||x_i-\mu_j||^2$

1. Initialize: Choose $k$ centroids $\mu_j$ randomly (k-means++ better).
2. Assignment: Assign each $x_i$ to nearest centroid: $C_j=\{x_i: ||x_i-\mu_j|| \le ||x_i-\mu_l|| \forall l\}$
3. Update: Recompute $\mu_j = \frac1{|C_j|}\sum_{x_i\in C_j} x_i$
4. Repeat 2-3 until centroids stop moving or $J$ change < threshold (convergence to local optimum).

Suitable Example:
Data points: A(1,1), B(1.5,2), C(3,4), D(5,7), D(3.5,5), E(4.5,5), $k=2$
Init $\mu1=(1,1)$, $\mu2=(5,7)$
Iter1 assignments: cluster1 {A,B}, cluster2 {C,D}... recompute etc. After few iterations converges to two clusters.

Time Complexity Analysis:
Per iteration: $O(n \cdot k \cdot d)$ distance computations ($n$ points, $k$ centroids, $d$ dims). For $i$ iterations: $O(n k d i)$. Space $O((n+k)d)$. If $k,d$ constants, $O(n i)$ linear in $n$. Compared to hierarchical $O(n^2)$. Elkan/Hamerly accelerations reduce but worst still $O(n k d i)$. Typically fast, converges quickly (10-100 iterations). Mention Lloyd's algorithm.

Limitations: need pre-specify $k$ (elbow/silhouette), sensitive to init & outliers, assumes spherical clusters, Euclidean biased.