Hierarchical clustering is often portrayed as the better
quality clustering approach, but is limited because of its quadratic
time complexity. In contrast, K-means and its variants have a
time complexity that is linear in the number of documents, but are
thought to produce inferior clusters. Sometimes K-means and
agglomerative hierarchical approaches are combined so as to “get
the best of both worlds.” For example, in the document domain,
Scatter/Gather [1], a document browsing system based on
clustering, uses a hybrid approach involving both K-means and
agglomerative hierarchical clustering. K-means is used because of
its run-time efficiency and agglomerative hierarchical clustering is
used because of its quality.