The following theorem summarizes the guarantees of this algorithm. We note that, as stated, the algorithm's runtime of \(O(nk \log n)\)  is not correct - in fact the number of phases may be arbitrarily large. However, using the same technique as detailed in Section 3.3 of [1]} the number of phases can be bounded to \(O(\frac{n}{k \log n})\)  while requiring \(O(k^2 \log ^2 n)\)  time per phase.
