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?