I am trying to see if the performance of both can be compared based on the objective functions they work on?
BTW, the Fuzzy-C-Means (FCM) clustering algorithm is also known as Soft K-Means.
The objective functions are virtually identical, the only difference being the introduction of a vector which expresses the percentage of belonging of a given point to each of the clusters. This vector is submitted to a "stiffness" exponent aimed at giving more importance to the stronger connections (and conversely at minimizing the weight of weaker ones); incidently, when the stiffness factor tends towards infinity the resulting vector becomes a binary matrix, hence making the FCM model identical to that of the K-Means.
I think that except for some possible issue with the clusters which have no points assigned to them, it is possible to emulate the K-Means algorithm with that of the FCM one, by simulating an infinite stiffness factor (= by introducing a function which changes the biggest value in the vector to 1, and zeros out the other values, in lieu of the exponentiation of the vector). This is of course a very inefficient way of running a K-Means, because the algorithm then has to perform as many operations as with a true FCM (if only with 1 and 0 values, which does simplify the arithmetic, but not the complexity)
With regards to performance, the FCM therefore needs to perform k (i.e. number of clusters) multiplications for each point, for each dimension (not counting also the exponentiation to take stiffness into account). This, plus the overhead needed for computing and managing the proximity vector, explains why FCM is quite slower than plain K-Means.
But FCM/Soft-K-Means is less "stupid" than Hard-K-Means when it comes for example to elongated clusters (when points otherwise consistent in other dimensions tend to scatter along a particular dimension or two), and that's why it's still around ;-)
From my original reply:
Also, I just thought about this, but haven't put any "mathematical" thought to it, FCM may converge faster than hard K-Means, somewhat offsetting the bigger computational requirement of FCM.
May 2018 edit:
There is actually no reputable research that I could identify which support my above hunch about FCM's faster rate of convergence. Thank you Benjamin Horn to keep me honest ;-)