Computational Complexity of K$-$Medoids

$2$ points possible $($graded$)$

Remember that the K$-$Medoids algorithm is given by

Randomly select $z_{1,\text{d}\text{o}\text{t}\text{s}\text{,}}{z}_K$

Iterate

Given $z_1,dots{z}_K,$ assign each $x^{(3)}$ to the closest $z_j,$ so that

Cosit$(z_1,dots{z}_K)={\displaystyle \underset{i=1}{\overset{n}{}}}mi{n}_j=1,$dots,kdisi$(x^{(i)},z_j)$

Given $C_{j}in\{C_{1,\text{d}\text{o}\text{t}\text{s}\text{,}}{C}_K\}$ find the best representative $z_{j}in\{x_1,$dots,$x_n\}$ such that

${\displaystyle \underset{x^{(0)}=C_j}{\overset{?}{}}}$dist$(x^{(i)},z_j)$

is minimal.

What is the complexity of step $2\mathrm{.}1?$

$O(n)$

$O(nK)$

$O(K^2)$

$O(ndK)$

Now what is the complexity of step $2\mathrm{.}2?$

$O(ndK)$

$O(n{K}^2)$

$O(n{K}^{2}d)$

$O(n^{2}dK)$