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?