Body: <p>I have been digging up of articles across the internet in context of computational complexity of GRU. Interestingly, I came across this article, <a href="http://cse.iitkgp.ac.in/%7Epsraja/FNNs%20,RNNs%20,LSTM%20and%20BLSTM.pdf" rel="nofollow noreferrer">http://cse.iitkgp.ac.in/~psraja/FNNs%20,RNNs%20,LSTM%20and%20BLSTM.pdf</a>, where it takes the following notations:</p>
  <p>Let I be the number of inputs, K be the number of outputs and H be the number of cells in the hidden layer</p>
  <p>And then goes on to explain the computational complexity of FNNs, RNNs, BRNNs, LSTM and BLSTM computational complexity is O(W) i.e., the total number of edges in the network.</p>
  <p>where</p>
  <ul>
  <li><p>For FNN: <span class="math-container">$W = IH + HK$</span> ( I get this part as, for fully connected networks, we have connections from each input to each node in hidden and subsequently for hidden to output nodes)</p>
  </li>
  <li><p>For RNN: <span class="math-container">$W = IH + H^2$</span> + HK ( The formula is pretty same as is it for FNN <strong>but where does this <span class="math-container">$H^2$</span> come into picture?</strong>)</p>
  </li>
  <li><p>For LSTM : <span class="math-container">$W = 4IH + 4H^2 + 3H + HK$</span> (<strong>It becomes more difficult as it comes down to LSTM as to where the 4's and 3's come into the equation?</strong> )</p>
  </li>
  </ul>
  <p><strong>Continuing with these notations, can I get a similar notation for GRU as well? This can be very helpful for understanding.</strong></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-05T11:57:24.670Z
Comments.Text: You can use latex on this site. So, I suggest that you edit your post to format your equations/formulas with latex.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-17T14:04:53.767Z
Comments.Text: Did you get the BigO for LSTM?
Comments.UserDisplayName: R2D2
Tags: <deep-learning><recurrent-neural-networks><long-short-term-memory><computational-complexity><gated-recurrent-unit>
Title: What is the computational complexity in terms of Big-O notation of a Gated Recurrent Unit Neural network?
UserDisplayName: rahul tomar
ThreadText: # What is the computational complexity in terms of Big-O notation of a Gated Recurrent Unit Neural network?
  
  (Asked by: username_0 on 2020-10-19)
  
  I have been digging up of articles across the internet in context of computational complexity of GRU. Interestingly, I came across this article, [http://cse.iitkgp.ac.in/~psraja/FNNs%20,RNNs%20,LSTM%20and%20BLSTM.pdf](http://cse.iitkgp.ac.in/%7Epsraja/FNNs%20,RNNs%20,LSTM%20and%20BLSTM.pdf), where it takes the following notations:
  
  Let I be the number of inputs, K be the number of outputs and H be the number of cells in the hidden layer
  
  And then goes on to explain the computational complexity of FNNs, RNNs, BRNNs, LSTM and BLSTM computational complexity is O(W) i.e., the total number of edges in the network.
  
  where
  
  * For FNN: $W = IH + HK$ ( I get this part as, for fully connected networks, we have connections from each input to each node in hidden and subsequently for hidden to output nodes)
  * For RNN: $W = IH + H^2$ + HK ( The formula is pretty same as is it for FNN **but where does this $H^2$ come into picture?**)
  * For LSTM : $W = 4IH + 4H^2 + 3H + HK$ (**It becomes more difficult as it comes down to LSTM as to where the 4's and 3's come into the equation?** )
  
  **Continuing with these notations, can I get a similar notation for GRU as well? This can be very helpful for understanding.**
  
  **Tags:** deep-learning, recurrent-neural-networks, long-short-term-memory, computational-complexity, gated-recurrent-unit
  
  > **Comments:**
  > **username_1**: You can use latex on this site. So, I suggest that you edit your post to format your equations/formulas with latex.  
  > **username_2**: Did you get the BigO for LSTM?  
  
  ---
  
  ## 0 answers
  
  