3
$\begingroup$

According to the internet, k-means clustering is linear in the number of data objects i.e. O(n), where n is the number of data objects. The time complexity of most of the hierarchical clustering algorithms is quadratic i.e. O(n2).

I am struggling to intuitively understand what is the difference between the two clustering approaches that causes this.

Question: What causes the difference in time complexity?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I think these time complexities are optimistic cases, but apart from that I think the reason is that in hierarchical clustering you consider the distances between many, if not all pairs of data points. The number of pairs scales quadratically with the number of points.

For k-means you somewhat cheat your way around considering all pairs by looking at the distances between each data point and the k means only. This scales linearly in both k and the number of data points.

So I think the speed up is caused by using the distance to the means as proxy for the distances between all points.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.