Why is hierarchical clustering quadratic and k-means linear? 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?
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.