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?

  • 1
    $\begingroup$ Don't ignore the need to iterate, and note that it could be high, and it certainly makes a difference. $\endgroup$ Feb 4, 2019 at 8:29
  • $\begingroup$ $k$-means is actually NP-complete (if $k$ is allowed to increase with $n$), though it's fast for reasonable cases. $\endgroup$ Sep 4, 2023 at 3:38

1 Answer 1


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 my experience there are many different estimates for SOM training. If you are doing the in-depth calculations for each portion of the algorithm, I think I agree with the following (for training SOM via the batch algorithm):

“… 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

Here, BSOM is batch SOM, BSOM-t is training using BSOM for a number of iterations, m is the number of nodes in the map, n is the number of observations in the training data, d is the number of distances and is related to the size of the neighbourhood.

Note that this is assuming sequential. If the map was parallelized using GPU, it could be a different story.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.