Suppose we have a network with *N* neurons and they all have *M* inputs.
Also suppose that the average size of set of winners is *W* and we
make 10 iterations in the fixed point iteration of . For a
single input the computation of takes roughly *NM* operations.
The computation of has to be done for the set of winners
only, so it takes order of *NW* operations. The iteration of
takes order of operations. The computation time of
from is negligible compared the time used in iteration. The
adaptation of the weight vectors needs to be done for the set of
winners only, and it takes *WM* operations, which is negligible
compared to the term *NM*. Computation of the correlations
between the weight vectors takes operations, but if the size of
batch is much larger than *N*, this is again negligible.

Summing the amounts of operations gives a total of
operations. The number of winners depends on the structure of data
and generally saturates to a constant value, when the number of
neurons grows. It is very rarely greater than the number of inputs.
Therefore the first term dominates, and *computational complexity
is typically of order NM*. This means that the computational
complexity grows linearly proportionally to the number of neurons as
opposed to previous algorithms where the growth has been at least
quadratic.

Thu May 9 14:06:29 DST 1996