# How is the training comlexity of NNLM word2vec calculated?

I was reading this paper on word2vec, and came around the following description of a feedforward NNLM:

It consists of input, projection, hidden and output layers. At the input layer, N previous words are encoded using 1-of-V coding, where V is size of the vocabulary. The input layer is then projected to a projection layer P that has dimensionality N × D, using a shared projection matrix. As only N inputs are active at any given time, composition of the projection layer is a relatively cheap operation.

The following expression is given for the computational complexity per training example:

Q = N×D + N×D×H + H×V.

The last two terms make sense to me: N×D×H is roughly the amount of parameters in a dense layer from the N×D-dimensional projection layer to the H hidden neurons, analogous for H×V. The first term, however, I expected to be V×D since the mapping from a one-hot encoded word to a D-dimensional vector is done via a V×D dimensional matrix. I came to that conclusion after reading this referenced paper and this SO post where the workings of the projection layer are explained in more detail.

Perhaps I have misunderstood what is meant by "training complexity".

Yes. Technically your understanding is correct; i.e. if all input neurons are active, the computational complexity would be like you said: Q = V$$\times$$D + N$$\times$$D$$\times$$H + H$$\times$$V.
So, if there are V words, the input, of course, will be a 1 of V one-hot vector. And since there are N words in the input, the input matrix will be of size N$$\times$$V. If D is the dimensionality of the embedded vector, the projection matrix will be of size V$$\times$$D. The product of the input matrix and the projection matrix will then have dimensions (N$$\times$$V)$$\cdot$$(V$$\times$$D) = N$$\times$$D.
As a result, at any given time, the input matrix will have dimension N$$\times$$N, and the projection matrix will only have to be N$$\times$$D. The product of these two matrices (N$$\times$$N)$$\cdot$$(N$$\times$$D) will still have dimensions N$$\times$$D. Hence the total complexity is Q = N$$\times$$D + N$$\times$$D$$\times$$H + H$$\times$$V.