Assuming $m$ observations, $n$ features and $k$ nodes in the self organizing map, what is the complexity of the classic SOM algorithm? What would be the complexity of an ensemble of SOMs, where each SOM has a different number of nodes?
According to this paper (1),
$$ T = O(NC) = O(S^2)$$ where $T$ is the computation time, $N$ is the input vector size and $C$ is the number of document presentation cycles. $S$ represents the size of the sample.
This site seems to agree with $O(S^2)$.
(1): Dmitri G. Roussinov, Hsinchun Chen. A Scalable Self-organizing Map Algorithm for Textual Classification: A Neural Network Approach to Thesaurus Generation