What is the complexity of a recurrent neural network?
I've found some time ago two interesting papers about recurrent neural networks and their complexity. I guess you can use those as a reference points at least:


Architectural Complexity Measures of Recurrent Neural Networks
Bounds on the complexity of recurrent neural network implementations of finite state machines