The time complexity of an algorithm always depends on its implementation (e.g. searching in a red-black tree has a different time complexity than searching in an unbalanced binary search tree). This also applies to the case of computing the time complexity of the algorithm that tests a neural network with multiple LSTM layers, so one may need to assume how an algorithm or data structure is implemented in order to provide the right time complexity.
Now, note that testing a neural network typically means performing a forward pass. So, basically, if you have the time complexity for the forward pass, you are almost done. In this answer, I provide details of how you can compute the time complexity of the forward pass of a feedforward neural network with no recurrent layers, so you can read it in order to have an idea of how you might do this in general.
Now, in the case of a neural network with LSTM layers, we also need to take into account the recurrent connections in the LSTM units. This would also be the case for the vanilla RNN units, which are simpler than LSTM units, so the time complexity is smaller.
I will assume that the equations used to perform the forward pass of an LSTM layer are the ones given in the PyTorch documentation
$$
\begin{aligned}
i_{t} &=\sigma\left(W_{i i} x_{t}+b_{i i}+W_{h i} h_{t-1}+b_{h i}\right) \\
f_{t} &=\sigma\left(W_{i f} x_{t}+b_{i f}+W_{h f} h_{t-1}+b_{h f}\right) \\
g_{t} &=\tanh \left(W_{i g} x_{t}+b_{i g}+W_{h g} h_{t-1}+b_{h g}\right) \\
o_{t} &=\sigma\left(W_{i o} x_{t}+b_{i o}+W_{h o} h_{t-1}+b_{h o}\right) \\
c_{t} &=f_{t} \odot c_{t-1}+i_{t} \odot g_{t} \\
h_{t} &=o_{t} \odot \tanh \left(c_{t}\right)
\end{aligned}
$$
Now, let's break these operations down. Note that the dimensionality and type of the objects (matrices and vectors) are important. I will start with the computation of $i_{t}$ (the output of the input gate). The computation of $f_{t}$ (forget gate), $g_{t}$ (cell) and $o_{t}$ (output gate) is the same, in terms of time complexity.
$$i_{t} =\sigma\left(W_{i i} x_{t}+b_{i i}+W_{h i} h_{t-1}+b_{h i}\right)$$
- $W_{i i} \in \mathbb{R}^{h \times d}$ is the matrix that represents the forward connections for the input gate
- $x_{t} \in \mathbb{R}^d$ is the input vector with $d$ entries (this could be e.g. the embedding of a word)
- $b_{i i} \in \mathbb{R}^h$ is a bias vector for this forward connetions
- $W_{h i} \in \mathbb{R}^{h \times h}$ is the matrix for the recurrent connections; note that this matrix has a different dimensionality than $W_{i i}$
- $h_{t-1} \in \mathbb{R}^h$ is the hidden state
- $b_{h i} \in \mathbb{R}^h$ is the bias vector for the recurrent operations
Here is an estimate of the time complexities of the operations inside the non-linearity
- $W_{i i} x_{t}$ has time complexity $\mathcal{O}(h d)$ (matrix-vector multiplication)
- $W_{i i} x_{t}+b_{i i}$ has time complexity $\mathcal{O}(h)$ (sum of two vectors, both with size $h$)
- $W_{h i} h_{t-1}$ has time complexity $\mathcal{O}(h^2)$
- $W_{h i} h_{t-1}+b_{h i}$ has time complexity $\mathcal{O}(h)$
Now, let $N = \max(d, h)$, then the time complexity of the operations inside the non-linearity is $\mathcal{O}(hN)$. More precisely, it would be
$$\mathcal{O}(h d + h + h^2 + h) = \mathcal{O}(h d + 2h + h^2) = \mathcal{O}(h(d + 2 + h)).$$
Actually, in this case, as I explain in the other answer, you could use $\Theta(hN)$ because this is an upper and lower bound in the limit.
Now, what is the time complexity of $\sigma$? It depends on what $\sigma$ is. If we assume it's a ReLU, then you perform basically the following operation
$$\displaystyle \sigma(x) = \max(0,x)$$
Let's assume that $\max(0,x)$ has a constant time complexity, so, if you apply the ReLU element-wise, you get a time complexity of $h$.
So, basically, the computation of $i_t$ has time complexity $\mathcal{O}(hN)$. The same applies to $f_{t}$ (forget gate), $g_{t}$ (cell) and $o_{t}$ (output gate), as stated above, so you could multiply this time complexity by $4$, but constant factors don't affect the time complexity. However, this is in theory, i.e. in the limit, in practice, they affect, so you probably want to include those. So, the time complexity, let's say, is
$$\mathcal{O}(4h(d + 2 + h))$$
so far (ignoring there's a tanh there: for simplicity, I assume it has the same time complexity as the ReLU even though that may not be the case: you can work out the details!)
Now, we have the following operation
$$c_{t} =f_{t} \odot c_{t-1}+i_{t} \odot g_{t},$$
where
- $c_t \in \mathbb{R}^h$ is the cell vector
- $\odot$ is an element-wise multiplication
So, this operation has time complexity
$$\mathcal{O}(2 h)$$
Similarly, the operation
$$h_{t} =o_{t} \odot \tanh \left(c_{t}\right)$$
has time complexity
$$\mathcal{O}(2 h)$$
One $h$ for the tanh and the other for the element-wise multiplication.
So, overall, the forward pass of a single LSTM layer has time complexity
$$\mathcal{O}(4h(d + 2 + h) + 4h) = \mathcal{O}(4h(d + 3 + h))$$
Now, you can work out the time complexity for multiple LSTM layers stacked one after the other. Just make sure that you understand that what is passed to the successive layer is not the input $x_t$ but the output of the previous layer.
In the end, you will also have to sum the complexity of the computation of the metric you're interested, which can be the loss or accuracy. If you understood my reasoning above, it should not be difficult to do that. The same applies for the case of a batch size and sequence size greater than 1.
