# How to derive the time computational complexity of k-medoids (PAM) clustering algorithm?

I have read that the time complexity of k-medoids/Partitioning Around Medoids (PAM) is O(k(n-k)^2). I am trying to understand how this algorithms translates into this time complexity.

As per my assumption, we have to find the distance between each of the (n-k) data points k times to place the data points in their closest cluster. After this, we need to replace each of the previously assumed medoids with each non-medoid, and re-compute the distance between for (n-k) objects, which will eventually equal to O(k(n-k)2). I am not sure if my understanding is right.

I used these links to gain understanding of the algorithm: https://en.wikipedia.org/wiki/K-medoids

How to perform K-medoids when having the distance matrix

Help me to clear my understanding of the complexity of k-medoids. Thanks.

• I got the same question and searched, my initial intuition was the same as yours. As far as I know, your understanding of the time complexity seems to be correct. p.s. - I know this question is 1 year old, I post this comment for anyone who'll be having the same problem in the future. Jun 5 '18 at 11:13