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
Help me to clear my understanding of the complexity of k-medoids. Thanks.