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

Question

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.

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.

https://www.geeksforgeeks.org/ml-k-medoids-clustering-with-example/