The following can be possible indicators of a clustering algorithm's performace:
1. As you have put it, execution time and memory spends can be vital in an environment where time is a constraint.
2. If you are doing supervised clustering, a clustering algorithm can be judged by various performance parameters like:
True False Rate,
Mis Classification errors,
RMS error, etc
3. If you are doing unsupervised clustering, then a clustering algorithm can be judged by thee parameters:
a. Level of human intervention such as supplying the 'k' in a k-means, or fuzzy functions in fuzzy clustering algorithms or
b. Thresholding in agglomerative/heirarchial clustering, etc.
c. Homogeneity in the clusters returned: Were all objects put in the same cluster really similar!
d. Sensitivity of the clustering convergence to externaly supplied information: eg, k value, etc
e. Stability of the returned clusters: Are the cluster memberships robust/rugged if you add/delete any attribute?
I am sure there can be more algorithm specific and your application specific methods to judge a clustering algorithm. But these should atleast give you some idea.