Answers.Body: <p>Let's suppose that we have an MLP with <span class="math-container">$15$</span> inputs, <span class="math-container">$20$</span> hidden neurons and <span class="math-container">$2$</span> output neurons. The operations performed are only in the hidden and output neurons, given that the input neurons only represent the inputs (so they do not perform any operation).</p>
  
  <p>Each hidden neuron performs a linear combination of its inputs followed by the application of a non-linear (or activation) function. So, each hidden neuron <span class="math-container">$j$</span> performs the following operation</p>
  
  <p><span class="math-container">\begin{align}
  o_j = \sigma \left(\sum_{i}^{15} w_{ij}x_i \right),\tag{1}\label{1}
  \end{align}</span></p>
  
  <p>where <span class="math-container">$i$</span> is the input coming from the input neuron <span class="math-container">$i$</span>, <span class="math-container">$w_{ij}$</span> is the weight of the connection from the input neuron <span class="math-container">$i$</span> to the hidden neuron <span class="math-container">$j$</span>, and <span class="math-container">$o_j$</span> is used to denote the output of neuron <span class="math-container">$j$</span>. </p>
  
  <p>There are <span class="math-container">$20$</span> hidden neurons and, for each of them, according to equation <span class="math-container">$\ref{1}$</span>, we perform <span class="math-container">$15$</span> multiplications (ignoring any multiplications that might be associated with the activation function), so <span class="math-container">$15*20 = 300$</span> multiplications are performed at the (only) hidden layer. In general, if there are <span class="math-container">$n$</span> inputs and <span class="math-container">$m$</span> hidden neurons, then <span class="math-container">$n*m$</span> multiplications will be performed in the first hidden layer.</p>
  
  <p>Now, each neuron <span class="math-container">$j$</span> at the next layer (in this case, the output layer), also performs a linear combination followed by the application of an activation function</p>
  
  <p><span class="math-container">\begin{align}
  o_j = \tau \left(\sum_{i}^{20} w_{ij}x_i \right),\tag{2}\label{2}
  \end{align}</span></p>
  
  <p>where <span class="math-container">$\tau$</span> is another activation function which might or not be equal to <span class="math-container">$\sigma$</span>, but we ignore all multiplications that might involve the application of the activation functions (we just want to count the ones in the linear combinations). Of course, in this case, <span class="math-container">$x_i$</span> corresponds to the activation of neuron <span class="math-container">$i$</span> (of the hidden layer).</p>
  
  <p>Similarly to the previous reasoning, there are <span class="math-container">$2$</span> output neurons and, to compute the output of each of them, <span class="math-container">$20$</span> multiplications are performed (in the linear combination), so there are a total of <span class="math-container">$2*20 = 40$</span> multiplications at the output layer. </p>
  
  <p>So, an MLP with <span class="math-container">$15$</span> inputs, <span class="math-container">$20$</span> hidden neurons and <span class="math-container">$2$</span> output neurons will perform <span class="math-container">$15*20 + 20*2 = 340$</span> multiplications (excluding activation functions). Of course, in this case, the number of multiplication depends not only on the number of neurons but also on the input size.</p>
  
  <p>In general, an MLP with <span class="math-container">$n$</span> inputs, <span class="math-container">$M$</span> hidden layers, where the <span class="math-container">$i$</span>th hidden layer contains <span class="math-container">$m_i$</span> hidden neurons, and <span class="math-container">$k$</span> output neurons will perform the following number of multiplications (excluding activation functions)</p>
  
  <p><span class="math-container">\begin{align}
  nm_{1} + m_{1}m_{2} + m_{2}m_{3} + \dots + m_{M-1}m_{M} + m_{M}k = nm_{1} + m_{M}k + \sum_{i=1}^{M-1} m_{i}m_{i+1} 
  \end{align}</span></p>
  
  <p>which, in big-O notation, can be written as</p>
  
  <p><span class="math-container">\begin{align}
  \Theta\left(nm_{1} + m_{M}k + \sum_{i=1}^{M-1} m_{i}m_{i+1} \right)
  \end{align}</span></p>
  
  <p>where <span class="math-container">$\Theta(\cdot)$</span> is used (as opposed to <span class="math-container">$\mathcal{O}(\cdot)$</span>) because this is a <a href="https://stackoverflow.com/a/464081/3924118">strict bound</a>. If you have just one hidden layer, the number of multiplications becomes </p>
  
  <p><span class="math-container">\begin{align}
  \Theta\left(nm_{1} + m_{1}k \right)
  \end{align}</span></p>
  
  <p>Of course, at each layer, the number of multiplications can be computed independently of the multiplications of the other layers (you can think of each layer as a perceptron), hence we sum (and not e.g. multiply) the multiplications of each layer when computing the total number of multiplications of the whole MLP.</p>
  
  <p>In general, when analyzing the time complexity of an algorithm, we do it with respect to the size of the input. However, in this case, the time complexity (more precisely, <em>the number of multiplications involved in the linear combinations</em>) also depends on the number of layers and the size of each layer. The time complexity of a forward pass of a trained MLP thus is architecture-dependent (which is a similar concept to an <a href="https://en.wikipedia.org/wiki/Output-sensitive_algorithm" rel="noreferrer">output-sensitive</a> algorithm).</p>
  
  <p>You can easily include other operations (sums, etc.) in this reasoning to calculate the actual time complexity of a trained MLP.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-28T10:08:55.167Z
Answers.Text: Thank you for your complete answer. It helped me a lot. Unfortunately my reputation is not enough yet for voting you up. So virtually i give you +1 for your good explanation :). Thanks.
Answers.UserDisplayName: Artificial
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-29T16:17:48.123Z
Answers.Text: From a different perspective, if we see Neural Networks as plain matrix products (post training feedforward), shouldn't it be something of the form $O(n^3)$? Just my two cents...
Answers.UserDisplayName: Karan Shah
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-29T16:25:34.583Z
Answers.Text: @KaranShah No, it shouldn't, but what is $n$ in your case? The complexity is proportional to the number of layers and the number of neurons per layer.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-29T17:04:18.167Z
Answers.Text: Yes, it is a function of the number of layers. So assuming $O(n^3)$ for 1 matrix product, it scales for L layers in the same manner, that's how I'm seeing it...
Answers.UserDisplayName: Karan Shah
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-29T17:09:16.953Z
Answers.Text: @KaranShah Matrix-matrix multiplication is $O(n^3)$ (actually, you can have a better bound than this). Anyway, the input is a vector, so you multiply a vector by a matrix (and not a matrix by another matrix), which is not $n^3$. See [https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra](https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-29T17:27:22.533Z
Answers.Text: Ah I got that! When m, n, p become equal that is similar to O(cubic). We're multiplying linear vectors, so it makes sense to be the way you showed it. Thanks. Solved.
Answers.UserDisplayName: Karan Shah
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-29T20:34:38.503Z
Answers.Text: @KaranShah Yes, but, in this case, either $p$ or $n$ are $1$, so that becomes e.g. $nm$ (which is what I am actually saying in my answer if you have noticed it).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-01T13:07:11.127Z
Answers.Text: @nbro I've read the comments and get a little confused. If we use a NN within a for loop. and the for loop has O(n) (before adding the NN) what will be overall compelxity after adding the NN? Suppose we have used the same NN i mentioned in the question. since its input and output size always the same and perform the same of multiplication (same hiddens and neurons) in each iteration. The overall complexity will be O((some-constant)n) or just O(n)? Could you please clarify this?
Answers.UserDisplayName: Artificial
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-01T13:20:43.150Z
Answers.Text: @Artificial If you execute a forward pass of the NN with $15$ inputs, $20$ hidden neurons and $2$ output neurons inside a for loop with $n$ iterations, then the total number of multiplications is $\Theta(n*(340))$ multiplications, given that, at each iteration, you perform $340$ multiplications (one forward pass) and there are $n$ iterations.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-28T07:48:59.963Z
Answers.Text: why only take into account the multiplication and not add the bias? All these time complexity computation approaches seem to be very fuzzy and more like the author's thoughts than any real analysis. What about the space complexity?
Answers.UserDisplayName: user3352632
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-27T23:13:56.277Z
Answers.LastActivityDate: 2019-08-21T19:54:48.847Z
Answers.LastEditDate: 2019-08-21T19:54:48.847Z
Answers.UserDisplayName: nbro
Body: <p>How do I determine the time complexity of the forward pass algorithm of a feedforward neural network? How many multiplications are done to generate the output?</p>
  
Tags: <neural-networks><feedforward-neural-networks><time-complexity><complexity-theory><forward-pass>
Title: What is the time complexity of the forward pass algorithm of a feedforward neural network?
UserDisplayName: Artificial
ThreadText: # What is the time complexity of the forward pass algorithm of a feedforward neural network?
  
  (Asked by: username_0 on 2019-07-27)
  
  How do I determine the time complexity of the forward pass algorithm of a feedforward neural network? How many multiplications are done to generate the output?
  
  **Tags:** neural-networks, feedforward-neural-networks, time-complexity, complexity-theory, forward-pass
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-07-27. Score: 11 | Accepted answer
  
  Let's suppose that we have an MLP with $15$ inputs, $20$ hidden neurons and $2$ output neurons. The operations performed are only in the hidden and output neurons, given that the input neurons only represent the inputs (so they do not perform any operation).
  
  Each hidden neuron performs a linear combination of its inputs followed by the application of a non-linear (or activation) function. So, each hidden neuron $j$ performs the following operation
  
  \begin{align}
  o\_j = \sigma \left(\sum\_{i}^{15} w\_{ij}x\_i \right),\tag{1}\label{1}
  \end{align}
  
  where $i$ is the input coming from the input neuron $i$, $w\_{ij}$ is the weight of the connection from the input neuron $i$ to the hidden neuron $j$, and $o\_j$ is used to denote the output of neuron $j$.
  
  There are $20$ hidden neurons and, for each of them, according to equation $\ref{1}$, we perform $15$ multiplications (ignoring any multiplications that might be associated with the activation function), so $15\*20 = 300$ multiplications are performed at the (only) hidden layer. In general, if there are $n$ inputs and $m$ hidden neurons, then $n\*m$ multiplications will be performed in the first hidden layer.
  
  Now, each neuron $j$ at the next layer (in this case, the output layer), also performs a linear combination followed by the application of an activation function
  
  \begin{align}
  o\_j = \tau \left(\sum\_{i}^{20} w\_{ij}x\_i \right),\tag{2}\label{2}
  \end{align}
  
  where $\tau$ is another activation function which might or not be equal to $\sigma$, but we ignore all multiplications that might involve the application of the activation functions (we just want to count the ones in the linear combinations). Of course, in this case, $x\_i$ corresponds to the activation of neuron $i$ (of the hidden layer).
  
  Similarly to the previous reasoning, there are $2$ output neurons and, to compute the output of each of them, $20$ multiplications are performed (in the linear combination), so there are a total of $2\*20 = 40$ multiplications at the output layer.
  
  So, an MLP with $15$ inputs, $20$ hidden neurons and $2$ output neurons will perform $15\*20 + 20\*2 = 340$ multiplications (excluding activation functions). Of course, in this case, the number of multiplication depends not only on the number of neurons but also on the input size.
  
  In general, an MLP with $n$ inputs, $M$ hidden layers, where the $i$th hidden layer contains $m\_i$ hidden neurons, and $k$ output neurons will perform the following number of multiplications (excluding activation functions)
  
  \begin{align}
  nm\_{1} + m\_{1}m\_{2} + m\_{2}m\_{3} + \dots + m\_{M-1}m\_{M} + m\_{M}k = nm\_{1} + m\_{M}k + \sum\_{i=1}^{M-1} m\_{i}m\_{i+1}
  \end{align}
  
  which, in big-O notation, can be written as
  
  \begin{align}
  \Theta\left(nm\_{1} + m\_{M}k + \sum\_{i=1}^{M-1} m\_{i}m\_{i+1} \right)
  \end{align}
  
  where $\Theta(\cdot)$ is used (as opposed to $\mathcal{O}(\cdot)$) because this is a [strict bound](https://stackoverflow.com/a/464081/3924118). If you have just one hidden layer, the number of multiplications becomes
  
  \begin{align}
  \Theta\left(nm\_{1} + m\_{1}k \right)
  \end{align}
  
  Of course, at each layer, the number of multiplications can be computed independently of the multiplications of the other layers (you can think of each layer as a perceptron), hence we sum (and not e.g. multiply) the multiplications of each layer when computing the total number of multiplications of the whole MLP.
  
  In general, when analyzing the time complexity of an algorithm, we do it with respect to the size of the input. However, in this case, the time complexity (more precisely, *the number of multiplications involved in the linear combinations*) also depends on the number of layers and the size of each layer. The time complexity of a forward pass of a trained MLP thus is architecture-dependent (which is a similar concept to an [output-sensitive](https://en.wikipedia.org/wiki/Output-sensitive_algorithm) algorithm).
  
  You can easily include other operations (sums, etc.) in this reasoning to calculate the actual time complexity of a trained MLP.
  
  > **Comments:**
  > **username_0**: Thank you for your complete answer. It helped me a lot. Unfortunately my reputation is not enough yet for voting you up. So virtually i give you +1 for your good explanation :). Thanks.  
  > **username_2**: From a different perspective, if we see Neural Networks as plain matrix products (post training feedforward), shouldn't it be something of the form $O(n^3)$? Just my two cents...  
  > **username_1**: @KaranShah No, it shouldn't, but what is $n$ in your case? The complexity is proportional to the number of layers and the number of neurons per layer.  
  > **username_2**: Yes, it is a function of the number of layers. So assuming $O(n^3)$ for 1 matrix product, it scales for L layers in the same manner, that's how I'm seeing it...  
  > **username_1**: @KaranShah Matrix-matrix multiplication is $O(n^3)$ (actually, you can have a better bound than this). Anyway, the input is a vector, so you multiply a vector by a matrix (and not a matrix by another matrix), which is not $n^3$. See [https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra](https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra).  
  > **username_2**: Ah I got that! When m, n, p become equal that is similar to O(cubic). We're multiplying linear vectors, so it makes sense to be the way you showed it. Thanks. Solved.  
  > **username_1**: @KaranShah Yes, but, in this case, either $p$ or $n$ are $1$, so that becomes e.g. $nm$ (which is what I am actually saying in my answer if you have noticed it).  
  > **username_0**: @nbro I've read the comments and get a little confused. If we use a NN within a for loop. and the for loop has O(n) (before adding the NN) what will be overall compelxity after adding the NN? Suppose we have used the same NN i mentioned in the question. since its input and output size always the same and perform the same of multiplication (same hiddens and neurons) in each iteration. The overall complexity will be O((some-constant)n) or just O(n)? Could you please clarify this?  
  > **username_1**: @Artificial If you execute a forward pass of the NN with $15$ inputs, $20$ hidden neurons and $2$ output neurons inside a for loop with $n$ iterations, then the total number of multiplications is $\Theta(n*(340))$ multiplications, given that, at each iteration, you perform $340$ multiplications (one forward pass) and there are $n$ iterations.  
  > **username_3**: why only take into account the multiplication and not add the bias? All these time complexity computation approaches seem to be very fuzzy and more like the author's thoughts than any real analysis. What about the space complexity?  
  
  ---
  
  