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.

  • $\begingroup$ 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. $\endgroup$
    – smb564
    Commented Jun 5, 2018 at 11:13

1 Answer 1


I hope this question is still relevant. Big O notation denotes the upper bound of an algorithm. Let's assume that the first sets of medoids are the worst medoids. The cost function calculated through these medoids is the maximum of all the possible sets of medoids. Every time we choose a random medoid for comparing the cost function, we will always find one that decreases the cost function. Let's assume that unfortunately, we always choose the next worst one in all the possibilities, therefore we will exhaust all the remaining medoids (n-k) to find the set of medoids that has the minimum cost function (Adversary argument). So the outmost loop would be k, for looping through all the medoids. Then it will be n-k, to loop through all the non-medoid data points. Then n-k again for choosing the random medoid. Examples may help understanding the process.



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.