# How to inform the space and time complexity of K-means, SOM and Hierachical clustering

In the paper I am writing, one of the reviewers asked for an

"a simple computational complexity analysis or time computational demands of their method"

My question is : Can I simply report the space and time complexities I found in the references bellow ?

• Kmeans: space-> $$O((n+M))$$, time-> $$O(Mn)$$
• SOM: space->$$O(M^2)$$, time-> $$O(Mn)$$
• hierarchical clustering: space->$$O(n^2)$$, time-> $$O(n^2logn)$$

where $$M$$ is the number of neurons(clusters), $$n$$ the number of data points.

OR or should I try to explain more? When I started to look for the space and time complexity of the three algorithms: kmeans, SOM, and hierarchical clustering, I found the two references bellow:

In the book :Challenging Problems and Solutions in Intelligent Systems, they state that the memory (space) complexity can be estimated by $$O(M^2)$$ and the time complexity can be estimated as $$O(Mn)$$, where $$M$$ is the number of neurons and $$n$$ the number of data points. However in the SOM training the dataset is presented for several epochs, so should the time complexity be $$O(MnId)$$, where $$I$$ is the number of epochs (iteractions) and $$d$$ the dimension? Also, the space complexity should be $$O((M+n)d)$$?

This would be similar to what I found in this paper A Survey on Clustering Algorithms and Complexity Analysis for Kmeans. In Kmeans, the spacecomplexity is $$O((n+M)d)$$, and the time complexity is $$O(MnId)$$ . Should I keep the $$I$$ ( number of interactions) and draw the $$d$$ dimension since it would be include in all cases?

• Don't ignore the need to iterate, and note that it could be high, and it certainly makes a difference. Feb 4, 2019 at 8:29

Are you looking for time estimates are for training or for testing? Time complexity $$O(Mn)$$ would simply appear to be a lookup operation for each of the $$n$$ elements, i.e. no updating of the neighbors. In that case, why $$O(M^2)$$ for storage? Wouldn't there just be a single codebook value for each element in the map?
“… in BSOM-t the computation of the neighborhood terms needs $$O(m^2)$$ operations, the assignment step runs in time $$O(nmd) + O(nm^2)$$ and the recalculation of the weight vectors runs in time $$O(nd) + O(m^2d)$$. Therefore, the complexity of BSOM is $$O(m^2) + O(nmd) + O(nm2) + O(m^2d)$$, and that of BSOM-t is $$Niter · (O(m^2) + O(nmd) + O(nm^2) + O(m^2d)$$.” Le Thi, H. A., & Nguyen, M. C. (2014, p.1353). Self-organizing maps by difference of convex functions optimization. Data Mining and Knowledge Discovery, 28(5–6), 1336–1365. http://doi.org/10.1007/s10618-014-0369-7