# what is the complexity of a bidirectional recurrent neural network?

In particular, what is the complexity of a bi-directional recurrent neural network taking into account the variants of LSTM and GRU as well for training?

I am hoping if I can get links to some additional research papers which talk or have mentioned the computational complexity of these methods in their works. I have been searching, but haven't come across anything meaningful till now

• What do you mean by "complexity"? Do you mean computational complexity in terms of big-O notation?
– noe
Oct 9 '20 at 9:41
• Thank you for pointing this out @ncasas. This is indeed what I meant, Computational complexity in terms of Big-O Oct 9 '20 at 12:00

The computational complexity of simple single-layer recurrent networks, either vanilla RNNs, LSTMs or GRUs is linear with the length of the input sequence, both at training time and inference time, so $$O(n)$$, where $$n$$ is the length of the input sequence. This is because in order to get the last time step output, you need to compute all the previous ones.

This is assuming that there is a single output. If there are multiple output time steps, then it is linear on the sum of both input and output lengths.

Take into account that, inside LSTMs and GRUS there are internal steps that account for a multiplication by a constant in the complexity.

You can complicate the network architecture in many different ways (more layers, skip connections, etc), and this can affect its computational complexity. Here you can find an in-depth study of the computational complexity of different architectural variations.

• Thank you for your reply @ncasas. It is indeed helpful. But I was hoping if I can get links to some additional research papers which talk or have mentioned the computational complexity of these methods in their works. I have been searching, but haven't come across anything meaningful till now. Oct 9 '20 at 13:11