The worst case complexity of the exchange algorithm is quadratic in the number of classes.
input: The fixed number of clusters N c Compute initial clustering while clustering changed in last iteration do forall w ∈ V do forall c ∈ C do move word w tentatively to cluster c compute updated optimization criterion move word w to cluster maximizing optimization criterion Algorithm 1: Exchange Algorithm Outline the average case complexity can be reduced by updating only the counts which are actually affected by moving a word from one cluster to another.