1) Time complexity of KMEANS
As explained in this post :
KMeans is an NP-hard problem. However, running a fixed number $t$ of iterations of the standard algorithm takes only $O(t*k*n*d)$, for $n$ (d-dimensional) points, where $k$ is the number of centroids (or clusters). This what practical implementations do (often with random restarts between the iterations).
2) When would you use one over the other?
As mentioned in this Wikipedia article, K-medoids is less sensitive to outliers and noise because of the function it minimizes.
It is more robust to noise and outliers as compared to k-means because it minimizes a sum of pairwise dissimilarities instead of a sum of squared Euclidean distances.
Also, K-medoids can use a variety of similarity measures where K-means is limited to euclidian (pairwise) distance. Excellent explanation [here].(https://stats.stackexchange.com/a/81496/279276)
3) What qualities does one look for to use k-medoids?
I would recommend using it whenever Euclidean Distance does not make sense in your data. If Euclidean Distance does not make sense (i.e. unrelated categorical variables : "has wings", "# of legs"), minimizing the sum of squared Euclidian distances probably won't either.
4) What are the differences in the output
The main difference is that medoids (equivalent to centroïds in K-Means) belong to the data points. You will never have a medoid that is somewhere between points. Instead, it will be superimposed on an existing point. This post shows it clearly.
It makes sense, especially for a categorical feature (# of legs), not to have a cluster center at 3.347 legs.
Hope this helps.